CF1286E.Fedya the Potter Strikes Back

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!

费迪亚有一个字符串 $S$（初始为空）和一个数组 $W$（初始也为空）。

需要依次处理 $n$ 个查询。第 $i$ 个查询包含一个小写英文字母 $c_i$ 和一个非负整数 $w_i$。首先，将 $c_i$ 追加到 $S$ 的末尾，同时将 $w_i$ 追加到 $W$ 的末尾。该查询的答案是：对所有满足 $1 \leq L \leq R \leq i$ 的子段 $[L,\ R]$，其“可疑度”之和。

我们定义子段的可疑度如下：若 $S$ 中对应于该子段的子串（即从第 $L$ 个字符到第 $R$ 个字符（含）构成的连续字符组成的字符串）与 $S$ 长度相同的前缀（即子段 $[1,\ R - L + 1]$ 对应的子串）完全匹配，则该子段的可疑度等于数组 $W$ 在子段 $[L,\ R]$ 上的最小值；否则（即该子串与对应前缀不匹配），可疑度为 $0$。

请帮助费迪亚在看守人员到来之前回答所有查询！

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

第一行包含一个整数 $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$。

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

输出 $n$ 行，第 $i$ 行应包含一个整数——即第 $i$ 个查询的答案。

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

为方便起见，我们将那些对应子串是 $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$。