AT_past202212_o シフトとシフト

長さ $ 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 $ はビットごとの排他的論理和を表す。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ D $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ Q $ $ query_1 $ $ query_2 $ $ \vdots $ $ query_Q $ ただし、 $ query_i $ は問題文中で示したタイプ $ 1 $ 、タイプ $ 2 $ 、タイプ $ 3 $ のいずれかの形式である。

タイプ $ 3 $ のクエリそれぞれについて、入力で与えられた順に、答えを改行区切りで出力せよ。

### Sample Explanation 1 はじめ、 $ 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 $ を出力します。 ### 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 $ - $ A_i $ の十進数表記のどの桁も `0` でない。 - $ 1 \leq x \leq N-1 $ - $ 1 \leq y \leq D-1 $ - $ 1 \leq l \leq r \leq N $ - 与えられるクエリのうち少なくとも $ 1 $ つはタイプ $ 3 $ である。 - 入力はすべて整数