O - Shift and Shift Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

問題文

長さ N の整数列 A = (A_1, A_2, \ldots, A_N) が与えられます。 A の各要素 A_1, A_2, \ldots, A_N はそれぞれ、（先頭に余計な 0 を含まない）十進数表記で D 桁の正の整数であり、どの桁も 0 ではありません。

Q 個のクエリが与えられます。各クエリは次に示すタイプ 1 、タイプ 2 、タイプ 3 のいずれかです。 与えられる Q 個のクエリを入力で与えられる順番にすべて処理してください。

【タイプ 1 】

1 x

数列 A を左に x 回だけ巡回シフトする。すなわち、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 について下記を行う:

A_i の十進数表記 d_1 d_2 \ldots d_Dを左に y 回だけ巡回シフトして得られる整数 d_{y+1} d_{y+2} \ldots d_D d_1 d_2 \ldots d_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 の十進数表記のどの桁も 0 でない。
  • 1 \leq x \leq N-1
  • 1 \leq y \leq D-1
  • 1 \leq l \leq r \leq N
  • 与えられるクエリのうち少なくとも 1 つはタイプ 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 個目のクエリで A_2 \oplus A_3 \oplus A_4 = 234 \oplus 345 \oplus 456 = 123 を出力します。
  • 2 個目のクエリで A = (A_1, A_2, A_3, A_4, A_5) = (456, 567, 123, 234, 345) と変化します。
  • 3 個目のクエリで 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

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N) of length N. Each element A_1, A_2, \ldots, A_N of A is a D-digit integer (without leading zeros) in the decimal notation, and none of its digits are 0.

You are given Q queries. Each query is of one of type 1, type 2, and type 3, which are described below. Process the given Q queries in the order given in the input.

[ Type 1 ]

1 x

Apply a left cyclic shift x times to the sequence A. In other words, if A = (a_1, a_2, \ldots, a_N), let A = (a_{x+1}, a_{x+2}, \ldots, a_N, a_1, a_2, \ldots, a_x).

[ Type 2 ]

2 l r y

Do the following for i = l, l+1, \ldots, r:

Let d_1 d_2 \ldots d_D be the decimal notation of A_i. Replace A_i with the integer d_{y+1} d_{y+2} \ldots d_D d_1 d_2 \ldots d_y, which is obtained by applying a left cyclic shift y times to the digits of A_i.

[ Type 3 ]

3 l r

Print A_l \oplus A_{l+1} \oplus \cdots \oplus A_r, where \oplus denotes the bitwise exclusive logical sum.

Constraints

  • 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
  • None of the digits of A_i is 0.
  • 1 \leq x \leq N-1
  • 1 \leq y \leq D-1
  • 1 \leq l \leq r \leq N
  • At least one of the given queries is of type 3.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N D
A_1 A_2 \ldots A_N
Q
query_1
query_2
\vdots
query_Q

Here, query_i is in one of the formats of type 1, type 2, and type 3 in the problem statement.

Output

Print the answer to each query of type 3, separated by newlines.

Sample Input 1

5 3
123 234 345 456 567
5
3 2 4
1 3
3 2 4
2 3 5 2
3 2 4

Sample Output 1

123
678
680

Initially, A = (A_1, A_2, A_3, A_4, A_5) = (123, 234, 345, 456, 567).

  • For the 1-st query, print A_2 \oplus A_3 \oplus A_4 = 234 \oplus 345 \oplus 456 = 123.
  • The 2-nd query makes A = (A_1, A_2, A_3, A_4, A_5) = (456, 567, 123, 234, 345).
  • For the 3-rd query, print A_2 \oplus A_3 \oplus A_4 = 567 \oplus 123 \oplus 234 = 678.
  • The 4-th query makes A = (A_1, A_2, A_3, A_4, A_5) = (456, 567, 312, 423, 534).
  • For the 5-th query, print A_2 \oplus A_3 \oplus A_4 = 567 \oplus 312 \oplus 423 = 680.

Sample Input 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

Sample Output 2

346778
710529
89337
796525
709076