问题陈述
给你一个整数序列 A = (A_1, A_2, \ldots, A_N) 长度 N。
每个元素 A_1, A_2, \ldots, A_N of A 是 D- 以十进制表示的数字整数(不带前导零),并且其所有数字都不是 0.
你被给予 Q 查询。 每个查询都属于其中一种类型 1,类型 2,然后输入 3,如下所述。 处理给定的 Q 按照输入中给出的顺序进行查询。
[ 类型 1 ]
1 x
应用左循环移位 x 次序列 A。 换句话说,如果 A = (a_1, a_2, \ldots, a_N), 让 A = (a_{x+1}, a_{x+2}, \ldots, a_N, a_1, a_2, \ldots, a_x).
[ 类型 2 ]
2 l r y
执行以下操作 i = l, l+1, \ldots, r:
让 d_1 d_2 \ldots d_D 是十进制表示法 A_i。 更换 A_i 与整数 d_{y+1} d_{y+2} \ldots d_D d_1 d_2 \ldots d_y,通过应用左循环移位获得 y 次到数字 A_i.
[ 类型 3 ]
3 l r
打印 A_l \oplus A_{l+1} \oplus \cdots \oplus A_r,其中 \oplus 表示按位异逻辑和。
约束
- 2 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 2 \leq D \leq 9
- 10^{D-1} \leq A_i < 10^D
- 没有任何数字 A_i is
0. - 1 \leq x \leq N-1
- 1 \leq y \leq D-1
- 1 \leq l \leq r \leq N
- 至少一个给定查询的类型为 3.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N D A_1 A_2 \ldots A_N Q query_1 query_2 \vdots query_Q
在这里, query_i 采用以下格式之一 问题陈述中的 1,类型 2,然后输入 3 。
输出
打印每个类型查询的答案 3,以换行符分隔。
示例输入 1
5 3 123 234 345 456 567 5 3 2 4 1 3 3 2 4 2 3 5 2 3 2 4
示例输出 1
123 678 680
最初, A = (A_1, A_2, A_3, A_4, A_5) = (123, 234, 345, 456, 567).
- 对于 1-st 查询、打印 A_2 \oplus A_3 \oplus A_4 = 234 \oplus 345 \oplus 456 = 123.
- 的 树的 2-nd 查询使得 A = (A_1, A_2, A_3, A_4, A_5) = (456, 567, 123, 234, 345).
- 对于 3-rd 查询、打印 A_2 \oplus A_3 \oplus A_4 = 567 \oplus 123 \oplus 234 = 678.
- 的 树的 4-第一个查询使得 A = (A_1, A_2, A_3, A_4, A_5) = (456, 567, 312, 423, 534).
- 对于 5第次查询,打印 A_2 \oplus A_3 \oplus A_4 = 567 \oplus 312 \oplus 423 = 680.
示例输入 2
20 6 318153 438943 474719 114997 373645 598458 427319 171794 653644 463294 123454 842368 264537 215892 467783 121159 836368 946718 889644 865849 20 2 6 9 3 2 8 13 5 2 1 6 3 2 14 20 5 1 7 2 14 15 4 3 8 8 2 4 5 3 2 7 17 2 1 19 2 13 16 4 2 4 9 2 3 11 14 1 8 2 2 17 3 3 6 9 3 6 16 2 16 17 2 1 1 3 3 20
示例输出 2
346778 710529 89337 796525 709076