E. Гончар Фёдор наносит ответный удар
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Феди есть строка $$$S$$$, изначально пустая, и массив $$$W$$$, тоже изначально пустой.

Феде по одному приходят $$$n$$$ запросов к этой строке и этому массиву. Запрос $$$i$$$ состоит из строчной буквы английского алфавита $$$c_i$$$ и целого неотрицательного числа $$$w_i$$$. К строке $$$S$$$ необходимо в конец приписать символ $$$c_i$$$, а к $$$W$$$ в конец добавить $$$w_i$$$. Ответом на запрос является сумма подозрительностей по всем подотрезкам $$$[L, \ R]$$$ массива $$$W$$$ $$$(1 \leq L \leq R \leq i)$$$.

Определим подозрительность подотрезка следующим образом: если подстрока $$$S$$$, соответствующая этому подотрезку (то есть строка из идущих подряд символов от $$$L$$$-го до $$$R$$$-го включительно), совпадает с префиксом $$$S$$$ такой же длины (то есть с подстрокой, соответствующей подотрезку $$$[1, \ R - L + 1]$$$), то его подозрительность равна минимуму в массиве $$$W$$$ на том же подотрезке $$$[L, \ R]$$$, а иначе она равна $$$0$$$.

Помогите Феде ответить на все запросы, пока за ним не приехали санитары!

Входные данные

Первая строка содержит целое число $$$n$$$ $$$(1 \leq n \leq 600\,000)$$$ — количество запросов.

Далее идут $$$n$$$ строк: $$$i$$$-я из них содержит запрос $$$i$$$: строчную букву латинского алфавита $$$c_i$$$ и целое число $$$w_i$$$ $$$(0 \leq w_i \leq 2^{30} - 1)$$$.

Запросы даны в зашифрованном виде. Пусть $$$ans$$$ — ответ на предыдущий запрос (для первого запроса положим эту величину равной $$$0$$$). Тогда для того, чтобы получить настоящий запрос, с данными числами необходимо проделать следующие операции: $$$c_i$$$ сдвинуть циклически по алфавиту вперёд на $$$ans$$$, а $$$w_i$$$ сделать равным $$$w_i \oplus (ans \ \& \ MASK)$$$, где $$$\oplus$$$ — побитовое исключающее «или», $$$\&$$$ — побитовое «и», а $$$MASK = 2^{30} - 1$$$.

Выходные данные

Выведите $$$n$$$ строк, в строке $$$i$$$ должно находиться одно целое число — ответ на запрос $$$i$$$.

Примеры
Входные данные
7
a 1
a 0
y 3
y 5
v 4
u 6
r 8
Выходные данные
1
2
4
5
7
9
12
Входные данные
4
a 2
y 2
z 0
y 2
Выходные данные
2
2
2
2
Входные данные
5
a 7
u 5
t 3
s 10
s 11
Выходные данные
7
9
11
12
13
Примечание

Для удобства будем называть «подозрительными» те подотрезки, для которых соответствующие им строки являются префиксами $$$S$$$, то есть те, подозрительность которых может быть не нулевой.

В результате расшифровки в первом примере из условия после всех запросов строка $$$S$$$ равна «abacaba», а все $$$w_i = 1$$$, то есть подозрительность всех подозрительных подотрезков просто равна $$$1$$$. Посмотрим, как получается ответ после каждого запроса:

1. $$$S$$$ = «a», у массива $$$W$$$ есть единственный подотрезок — $$$[1, \ 1]$$$, и соответствующая ему подстрока равна «a», то есть всей строке $$$S$$$, то есть она является префиксом $$$S$$$, и подозрительность подотрезка равна $$$1$$$.

2. $$$S$$$ = «ab», подозрительные подотрезки: $$$[1, \ 1]$$$ и $$$[1, \ 2]$$$, всего $$$2$$$.

3. $$$S$$$ = «aba», подозрительные подотрезки: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$ и $$$[3, \ 3]$$$, всего $$$4$$$.

4. $$$S$$$ = «abac», подозрительные подотрезки: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$, $$$[1, \ 4]$$$ и $$$[3, \ 3]$$$, всего $$$5$$$.

5. $$$S$$$ = «abaca», подозрительные подотрезки: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$, $$$[1, \ 4]$$$, $$$[1, \ 5]$$$, $$$[3, \ 3]$$$ и $$$[5, \ 5]$$$, всего $$$7$$$.

6. $$$S$$$ = «abacab», подозрительные подотрезки: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$, $$$[1, \ 4]$$$, $$$[1, \ 5]$$$, $$$[1, \ 6]$$$, $$$[3, \ 3]$$$, $$$[5, \ 5]$$$ и $$$[5, \ 6]$$$ всего $$$9$$$.

7. $$$S$$$ = «abacaba», подозрительные подотрезки: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$, $$$[1, \ 4]$$$, $$$[1, \ 5]$$$, $$$[1, \ 6]$$$, $$$[1, \ 7]$$$, $$$[3, \ 3]$$$, $$$[5, \ 5]$$$, $$$[5, \ 6]$$$, $$$[5, \ 7]$$$ и $$$[7, \ 7]$$$ всего $$$12$$$.

Во втором примере из условия после всех запросов $$$S$$$ = «aaba», $$$W = [2, 0, 2, 0]$$$.

1. $$$S$$$ = «a», подозрительные подотрезки: $$$[1, \ 1]$$$ (подозрительность $$$2$$$), в сумме $$$2$$$.

2. $$$S$$$ = «aa», подозрительные подотрезки: $$$[1, \ 1]$$$ ($$$2$$$), $$$[1, \ 2]$$$ ($$$0$$$), $$$[2, \ 2]$$$ ($$$0$$$), в сумме $$$2$$$.

3. $$$S$$$ = «aab», подозрительные подотрезки: $$$[1, \ 1]$$$ ($$$2$$$), $$$[1, \ 2]$$$ ($$$0$$$), $$$[1, \ 3]$$$ ($$$0$$$), $$$[2, \ 2]$$$ ($$$0$$$), в сумме $$$2$$$.

4. $$$S$$$ = «aaba», подозрительные подотрезки: $$$[1, \ 1]$$$ ($$$2$$$), $$$[1, \ 2]$$$ ($$$0$$$), $$$[1, \ 3]$$$ ($$$0$$$), $$$[1, \ 4]$$$ ($$$0$$$), $$$[2, \ 2]$$$ ($$$0$$$), $$$[4, \ 4]$$$ ($$$0$$$), в сумме $$$2$$$.

В третьем примере из условия после всех запросов $$$S$$$ = «abcde», $$$W = [7, 2, 10, 1, 7]$$$.

1. $$$S$$$ = «a», подозрительные подотрезки: $$$[1, \ 1]$$$ ($$$7$$$), в сумме $$$7$$$.

2. $$$S$$$ = «ab», подозрительные подотрезки: $$$[1, \ 1]$$$ ($$$7$$$), $$$[1, \ 2]$$$ ($$$2$$$), в сумме $$$9$$$.

3. $$$S$$$ = «abc», подозрительные подотрезки: $$$[1, \ 1]$$$ ($$$7$$$), $$$[1, \ 2]$$$ ($$$2$$$), $$$[1, \ 3]$$$ ($$$2$$$), в сумме $$$11$$$.

4. $$$S$$$ = «abcd», подозрительные подотрезки: $$$[1, \ 1]$$$ ($$$7$$$), $$$[1, \ 2]$$$ ($$$2$$$), $$$[1, \ 3]$$$ ($$$2$$$), $$$[1, \ 4]$$$ ($$$1$$$), в сумме $$$12$$$.

5. $$$S$$$ = «abcde», подозрительные подотрезки: $$$[1, \ 1]$$$ ($$$7$$$), $$$[1, \ 2]$$$ ($$$2$$$), $$$[1, \ 3]$$$ ($$$2$$$), $$$[1, \ 4]$$$ ($$$1$$$), $$$[1, \ 5]$$$ ($$$1$$$), в сумме $$$13$$$.