AT_past202212_o シフトとシフト

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.

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.

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

### Sample Explanation 1 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 $ . ### 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.