Fedya the Potter Strikes Back

Description:

Input:

The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 600\,000)$$$ — the number of queries.

The $$$i$$$-th of the following $$$n$$$ lines contains the query $$$i$$$: a lowercase letter of the Latin alphabet $$$c_i$$$ and an integer $$$w_i$$$ $$$(0 \leq w_i \leq 2^{30} - 1)$$$.

All queries are given in an encrypted form. Let $$$ans$$$ be the answer to the previous query (for the first query we set this value equal to $$$0$$$). Then, in order to get the real query, you need to do the following: perform a cyclic shift of $$$c_i$$$ in the alphabet forward by $$$ans$$$, and set $$$w_i$$$ equal to $$$w_i \oplus (ans \ \& \ MASK)$$$, where $$$\oplus$$$ is the bitwise exclusive "or", $$$\&$$$ is the bitwise "and", and $$$MASK = 2^{30} - 1$$$.

Output:

Print $$$n$$$ lines, $$$i$$$-th line should contain a single integer — the answer to the $$$i$$$-th query.

Sample Input:

7
a 1
a 0
y 3
y 5
v 4
u 6
r 8

Sample Output:

1
2
4
5
7
9
12

Sample Input:

4
a 2
y 2
z 0
y 2

Sample Output:

2
2
2
2

Sample Input:

5
a 7
u 5
t 3
s 10
s 11

Sample Output:

7
9
11
12
13

Note:

For convenience, we will call "suspicious" those subsegments for which the corresponding lines are prefixes of $$$S$$$, that is, those whose suspiciousness may not be zero.

As a result of decryption in the first example, after all requests, the string $$$S$$$ is equal to "abacaba", and all $$$w_i = 1$$$, that is, the suspiciousness of all suspicious sub-segments is simply equal to $$$1$$$. Let's see how the answer is obtained after each request:

1. $$$S$$$ = "a", the array $$$W$$$ has a single subsegment — $$$[1, \ 1]$$$, and the corresponding substring is "a", that is, the entire string $$$S$$$, thus it is a prefix of $$$S$$$, and the suspiciousness of the subsegment is $$$1$$$.

2. $$$S$$$ = "ab", suspicious subsegments: $$$[1, \ 1]$$$ and $$$[1, \ 2]$$$, total $$$2$$$.

3. $$$S$$$ = "aba", suspicious subsegments: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$ and $$$[3, \ 3]$$$, total $$$4$$$.

4. $$$S$$$ = "abac", suspicious subsegments: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$, $$$[1, \ 4]$$$ and $$$[3, \ 3]$$$, total $$$5$$$.

5. $$$S$$$ = "abaca", suspicious subsegments: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$, $$$[1, \ 4]$$$ , $$$[1, \ 5]$$$, $$$[3, \ 3]$$$ and $$$[5, \ 5]$$$, total $$$7$$$.

6. $$$S$$$ = "abacab", suspicious subsegments: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$, $$$[1, \ 4]$$$ , $$$[1, \ 5]$$$, $$$[1, \ 6]$$$, $$$[3, \ 3]$$$, $$$[5, \ 5]$$$ and $$$[5, \ 6]$$$, total $$$9$$$.

7. $$$S$$$ = "abacaba", suspicious subsegments: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$, $$$[1, \ 4]$$$ , $$$[1, \ 5]$$$, $$$[1, \ 6]$$$, $$$[1, \ 7]$$$, $$$[3, \ 3]$$$, $$$[5, \ 5]$$$, $$$[5, \ 6]$$$, $$$[5, \ 7]$$$ and $$$[7, \ 7]$$$, total $$$12$$$.

In the second example, after all requests $$$S$$$ = "aaba", $$$W = [2, 0, 2, 0]$$$.

1. $$$S$$$ = "a", suspicious subsegments: $$$[1, \ 1]$$$ (suspiciousness $$$2$$$), totaling $$$2$$$.

2. $$$S$$$ = "aa", suspicious subsegments: $$$[1, \ 1]$$$ ($$$2$$$), $$$[1, \ 2]$$$ ($$$0$$$), $$$[2, \ 2]$$$ ( $$$0$$$), totaling $$$2$$$.

3. $$$S$$$ = "aab", suspicious subsegments: $$$[1, \ 1]$$$ ($$$2$$$), $$$[1, \ 2]$$$ ($$$0$$$), $$$[1, \ 3]$$$ ( $$$0$$$), $$$[2, \ 2]$$$ ($$$0$$$), totaling $$$2$$$.

4. $$$S$$$ = "aaba", suspicious subsegments: $$$[1, \ 1]$$$ ($$$2$$$), $$$[1, \ 2]$$$ ($$$0$$$), $$$[1, \ 3]$$$ ( $$$0$$$), $$$[1, \ 4]$$$ ($$$0$$$), $$$[2, \ 2]$$$ ($$$0$$$), $$$[4, \ 4]$$$ ($$$0$$$), totaling $$$2$$$.

In the third example, from the condition after all requests $$$S$$$ = "abcde", $$$W = [7, 2, 10, 1, 7]$$$.

1. $$$S$$$ = "a", suspicious subsegments: $$$[1, \ 1]$$$ ($$$7$$$), totaling $$$7$$$.

2. $$$S$$$ = "ab", suspicious subsegments: $$$[1, \ 1]$$$ ($$$7$$$), $$$[1, \ 2]$$$ ($$$2$$$), totaling $$$9$$$.

3. $$$S$$$ = "abc", suspicious subsegments: $$$[1, \ 1]$$$ ($$$7$$$), $$$[1, \ 2]$$$ ($$$2$$$), $$$[1, \ 3]$$$ ( $$$2$$$), totaling $$$11$$$.

4. $$$S$$$ = "abcd", suspicious subsegments: $$$[1, \ 1]$$$ ($$$7$$$), $$$[1, \ 2]$$$ ($$$2$$$), $$$[1, \ 3]$$$ ( $$$2$$$), $$$[1, \ 4]$$$ ($$$1$$$), totaling $$$12$$$.

5. $$$S$$$ = "abcde", suspicious subsegments: $$$[1, \ 1]$$$ ($$$7$$$), $$$[1, \ 2]$$$ ($$$2$$$), $$$[1, \ 3]$$$ ( $$$2$$$), $$$[1, \ 4]$$$ ($$$1$$$), $$$[1, \ 5]$$$ ($$$1$$$), totaling $$$13$$$.