Fedya the Potter Strikes Back

给定一个字符串 $S$ 和一个序列 $W$，初始时它们都为空。 你需要在线完成 $n$ 次操作。每次操作在 $S$ 后面添加一个字符 $c_i$，在序列 $W$ 后面添加一个数字 $w_i$。二者均加密。 加密规则如下：设 $ans$ 为上一个查询的答案，初始值为 $0$。将 $c_i$ 按字典序后移 $ans$ 位，将 $w_i$ 改成 $w_i\oplus (ans \operatorname{\&} M)$，其中 $M = 2^{30} - 1$。特别地，定义 `z` 后移一位为 `a`。 定义一个子区间 $[L, R]$ 的可疑度为： 若子串 $[L,R]$ 和前缀 $[1,R-L+1]$ 相同，则其可疑度为 $\min_{i=L}^{R} W_i$。否则其可疑度为 $0$。 每次操作后，你都要求出当前的串的所有子区间的可疑度之和。 $1\leq n\leq 6\times 10 ^ 5$，$0\leq w_i < 2 ^ {30}$，$c_i$ 为小写字母。

Fedya has a string $ S $ , initially empty, and an array $ W $ , also initially empty. There are $ n $ queries to process, one at a time. Query $ i $ consists of a lowercase English letter $ c_i $ and a nonnegative integer $ w_i $ . First, $ c_i $ must be appended to $ S $ , and $ w_i $ must be appended to $ W $ . The answer to the query is the sum of suspiciousnesses for all subsegments of $ W $ $ [L, \ R] $ , $ (1 \leq L \leq R \leq i) $ . We define the suspiciousness of a subsegment as follows: if the substring of $ S $ corresponding to this subsegment (that is, a string of consecutive characters from $ L $ -th to $ R $ -th, inclusive) matches the prefix of $ S $ of the same length (that is, a substring corresponding to the subsegment $ [1, \ R - L + 1] $ ), then its suspiciousness is equal to the minimum in the array $ W $ on the $ [L, \ R] $ subsegment. Otherwise, in case the substring does not match the corresponding prefix, the suspiciousness is $ 0 $ . Help Fedya answer all the queries before the orderlies come for him!

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 $ .

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

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

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 $ .