Cho 2 xâu ~s~, ~t~ ban đầu rỗng. Bạn cần xử lý ~Q~ query thuộc một trong 2 loại:

• ~1~ ~c~: thêm một chữ cái latin viết thường ~c~ vào cuối xâu ~s~

• ~2~ ~d~: thêm một chữ cái latin viết thường ~d~ vào cuối xâu ~t~

Sau mỗi query, tính giá trị biểu thức sau:

$$A(s, t) = \sum_{i=0}^{|t - 1|} cnt_i(s, t)*i$$

Trong đó ~cnt_i(s, t)~ là số lần xâu ~t_0t_1..t_i~ xuất hiện trong ~s~.

Input

Dòng đầu gồm một số nguyên dương ~Q~ ~(1 \leq Q \leq 3*10^5)~. ~Q~ dòng tiếp theo, mỗi dòng ghi một query gồm một số nguyên dương ~type~ ~(1 \leq type \leq 2)~ và một chữ cái latin viết thường.

Output

In ra ~Q~ dòng, dòng thứ ~i~ là giá trị của biểu thức ~A(s, t)~ sau query thứ ~i~.

Sample Input 1

8
1 a
2 a
1 a
2 a
1 a
2 a
1 a
1 a

Sample Output 1

0
0
0
1
2
4
7
10

Notes

Giải thích ví dụ 1:

• Query 1: ~s~ = ~a~, ~t~ rỗng. ~A(s, t) = 0~.

• Query 2: ~s~ = ~a~, ~t~ = ~a~. ~A(s, t) = cnt_0(s, t) * 0 = 0~.

• Query 3: ~s~ = ~aa~, ~t~ = ~a~. ~A(s, t) = cnt_0(s, t) * 0 = 0~.

• Query 4: ~s~ = ~aa~, ~t~ = ~aa~. ~A(s, t) = cnt_0(s, t) * 0 + cnt_1(s, t) * 1 = 0 + 1*1 = 1~.

• Query 5: ~s~ = ~aaa~, ~t~ = ~aa~. ~A(s, t) = cnt_0(s, t) * 0 + cnt_1(s, t) * 1 = 0 + 2*1 = 2~.

• Query 6: ~s~ = ~aaa~, ~t~ = ~aaa~. ~A(s, t) = cnt_0(s, t) * 0 + cnt_1(s, t) * 1 + cnt_2(s, t)*2 = 0 + 2*1 + 1*2 = 4~.

• Query 7: ~s~ = ~aaaa~, ~t~ = ~aaa~. ~A(s, t) = cnt_0(s, t) * 0 + cnt_1(s, t) * 1 + cnt_2(s, t)*2 = 0 + 3*1 + 2*2 = 7~.

• Query 8: ~s~ = ~aaaaa~, ~t~ = ~aaa~. ~A(s, t) = cnt_0(s, t) * 0 + cnt_1(s, t) * 1 + cnt_2(s, t)*2 = 0 + 4*1 + 3*2 = 10~.