Fedya 有一个字符串 $$$S$$$(最初为空)和一个数组 $$$W$$$(最初也为空)。
有 $$$n$$$ 个查询需要处理,一次一个。查询$$$i$$$由小写英文字母$$$c_i$$$和非负整数$$$w_i$$$组成。首先,$$$c_i$$$ 必须附加到$$$S$$$,$$$w_i$$$ 必须附加到$$$W$$$。查询的答案是 $$$W$$$ $$$[L, \ R]$$$, $$$(1 \leq L \leq R \leq i)$$$ 的所有子段的可疑度总和。
我们定义一个子段的可疑性如下:如果该子段对应的$$$S$$$的子串(即从$$$L$$$-th到$$$R$$$-th的连续字符串)与相同长度的$$$S$$$的前缀(即子段$$$[1, \ R - L + 1]$$$),则其可疑度等于$$$[L,\R]$$$子段上数组$$$W$$$中的最小值。否则,如果子字符串与相应的前缀不匹配,则可疑度为$$$0$$$。
在勤务兵来找他之前,帮助 Fedya 回答所有问题!
输入
第一行包含一个整数 $$$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$$$是按位异“或”,$$$\&$$$是按位“与”,并且$$$掩码 = 2^{30} - 1$$$。
输出
打印 $$$n$$$ 行,第 $$$i$$$ 行应包含一个整数 - 第 $$$i$$$ 查询的答案。
示例
输入 #1
7 a 1 a 0 y 3 y 5 v 4 u 6 r 8
输出 #1
1 2 4 5 7 9 12
输入 #2
4 a 2 y 2 z 0 y 2
输出 #2
2 2 2 2
输入 #3
5 a 7 u 5 t 3 s 10 s 11
输出 #3
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$$$。