AT_past202004_g.ストリング・クエリ

对字符串 $S$ 进行 $Q$ 次操作。初始时，字符串 $S$ 为空字符串。

第 $i$ 次操作的类型由整数 $T_i\ (1\leq i\leq Q)$ 表示，具体内容如下：

• 当 $T_i=1$ 时：
  • 给定一个小写英文字母 $C_i$ 和一个整数 $X_i$。在 $S$ 的末尾添加 $X_i$ 个 $C_i$ 字符。
• 当 $T_i=2$ 时：
  • 给定一个整数 $D_i$。从 $S$ 的开头删除 $D_i$ 个字符。如果 $S$ 的长度不超过 $D_i$，则 $S$ 变为空字符串。对于本次操作，统计 a、b、c、$\cdots$、z 各字符被删除的数量。若分别删除了 $del_a,\ del_b,\ \cdots,\ del_z$ 个，则输出 $del_a^2+del_b^2+\cdots+del_z^2$。

输入通过标准输入给出，格式如下：

$Q$
$Query_1$
$\vdots$
$Query_Q$

第 $2$ 行到第 $Q+1$ 行的 $Query_i$ 有以下两种形式之一：

$1\ C_i\ X_i$

表示执行 $T_i=1$ 的操作。

$2\ D_i$

表示执行 $T_i=2$ 的操作。

对于每个 $T_i=2$ 的操作，按顺序输出每种字符被删除数量的平方和。

注意

本题在 2020 年 5 月 2 日 18:00 JST 之前禁止公开讨论。如有违规，可能会被追究责任。

考试结束后可以公开总分和认证级别，但请不要透露解题情况等信息。

约束条件

• $1\leq Q\leq 10^5$
• $T_i=1$ 或 $2$
• $C_i$ 为小写英文字母
• $1\leq X_i\leq 10^5$
• $1\leq D_i\leq 10^5$
• $Q,\ T_i,\ X_i,\ D_i$ 均为整数
• 至少存在一次 $T_i=2$ 的操作

样例解释 1

初始 $S$ 为空字符串。

• 第 1 次操作后，$S$ 变为 aaaaa。
• 第 2 次操作后，$S$ 变为 aa。删除了 $3$ 个 a，其他字符未被删除。
• 第 3 次操作后，$S$ 变为 aatttttttt。
• 第 4 次操作后，$S$ 变为 aattttttttcccccccccc。
• 第 5 次操作前，$S$ 长度为 $20$，操作后 $S$ 变为空字符串。删除了 $2$ 个 a，$10$ 个 c，$8$ 个 t。
• 第 6 次操作后，$S$ 仍为空字符串，没有字符被删除。

因此，第 2 次操作输出 $3^2+0^2+\cdots+0^2=9$，第 5 次操作输出 $2^2+10^2+8^2=168$，第 6 次操作输出 $0$。

样例解释 2

初始 $S$ 为空字符串。

• 第 1 次操作后，$S$ 变为 xxxxx。
• 第 2 次操作后，$S$ 变为 xxxxxyyyyyyyy。
• 第 3 次操作后，$S$ 变为 yyyyyy。删除了 $5$ 个 x，$2$ 个 y，$5^2+2^2=29$。
• 第 4 次操作后，$S$ 变为 yyyyyyzzzzzzzz。

由 ChatGPT 4.1 翻译