← 返回题目列表

AtCoder · past202212_o

O. 移位和移位

中文机器翻译题面 查看原题

问题陈述

给你一个整数序列 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