Problem Description

Perform $ Q $ operations on a string $ S $. Initially, the string $ S $ is an empty string.

The type of the $ i $-th operation is represented by an integer $T_i\ (1\ \leq\ i\ \leq\ Q)$, and the details are as follows:

• When $T_i\ =\ 1$:
• Given an English lowercase letter $ C_i $ and an integer $ X_i $. Append $ X_i $ characters of $ C_i $ to the end of $ S $.
• When $T_i\ =\ 2$:
• Given an integer $ D_i $. Remove the first $ D_i $ characters from $ S $. If the length of $ S $ is less than or equal to $ D_i $, $ S $ becomes an empty string. Then, determine how many characters of each letter a, b, c, $\cdots$ z were deleted. If $del_a,\ del_b,\ \cdots,\ del_z$ characters were deleted respectively, output ${del_a}^2\ +\ {del_b}^2\ +\ \cdots\ +\ {del_z}^2$.

Input Format

The input is given from the standard input in the following format:

$ Q $ $ Query_1 $ $ : $ $ Query_Q $

From the 2nd line to the $ Q+1 $ line, $ Query_i $ is one of the following two:

$ 1 $ $ C_i $ $ X_i $

Indicates performing the operation with $T_i\ =\ 1$.

$ 2 $ $ D_i $

Indicates performing the operation with $T_i\ =\ 2$.

Output Format

For each operation where $T_i\ =\ 2$, output the sum of the squares of the number of deleted characters for each letter type in order.

Sample Input and Output

Sample Input #1

6
1 a 5
2 3
1 t 8
1 c 10
2 21
2 4

Sample Output #1

9
168
0

Sample Input #2

4
1 x 5
1 y 8
2 7
1 z 8

Sample Output #2

29

Sample Input #3

3
1 p 3
1 q 100000
2 100000

Sample Output #3

9999400018

Notes/Hints

Constraints

• $1\ \leq\ Q\ \leq\ 10^5$
• $T_i\ =\ 1$ or $ 2 $
• $ C_i $ is an English lowercase letter
• $1\ \leq\ X_i\ \leq\ 10^5$
• $1\ \leq\ D_i\ \leq\ 10^5$
• $Q,\ T_i,\ X_i,\ D_i$ are integers
• There is at least one operation with $T_i\ =\ 2$

Sample Explanation 1

Initially, $ S $ is an empty string.
- After the 1st operation, $ S $ becomes aaaaa.
- After the 2nd operation, $ S $ becomes aa. 3 a characters are deleted, and no other characters are deleted.
- After the 3rd operation, $ S $ becomes aatttttttt.
- After the 4th operation, $ S $ becomes aattttttttcccccccccc.
- After the 5th operation, since the length of $ S $ before the operation is 20, $ S $ becomes an empty string. 2 a characters, 10 c characters, and 8 t characters are deleted.
- After the 6th operation, $ S $ remains an empty string. No characters are deleted.

Thus, for the 2nd operation, output $3^2\ +\ 0^2\ +\ \cdots\ +\ 0^2\ =\ 9$. For the 5th operation, output $2^2\ +\ 10^2\ +\ 8^2\ =\ 168$. For the 6th operation, output $ 0 $.

Sample Explanation 2

Initially, $ S $ is an empty string.
- After the 1st operation, $ S $ becomes xxxxx.
- After the 2nd operation, $ S $ becomes xxxxxyyyyyyyy.
- After the 3rd operation, $ S $ becomes yyyyyy. 5 x characters and 2 y characters are deleted. $5^2\ +\ 2^2\ =\ 29$.
- After the 4th operation, $ S $ becomes yyyyyyzzzzzzzz.

见题面 Input 部分

见题面 Output 部分