ストーリー

?? 「Memory Limitが厳しい問題はクソ問」

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。 また、長さ $M$ の整数列 $l=(l_1,l_2,\ldots,l_M),r=(r_1,r_2,\ldots,r_M),x=(x_1,x_2,\ldots,x_M),L=(L_1,L_2,\ldots,L_M),R=(R_1,R_2,\ldots,R_M)$ が与えられます。

以下の $Q$ 個の小問題 $i=1,2,\ldots, Q$ を順に処理してください。小問題ごとに $A$ の値は独立であることに注意してください。

<小問題 $i$>

• 整数 $s_i, q_i$ が与えられます。最初 $y=i$ とします。以下の $q_i$ 個のクエリ $j=1,2,\ldots,q_i$ を順に処理してください。

  <クエリ $j$>

  • $z=((s_i+j) \bmod M)+1$ とする。
  • また、$u=\min(N,\max(1,l_z\oplus y))$, $v=\min(N,\max(1,r_z\oplus y))$, $U=\min(N,\max(1,L_z\oplus y))$, $V=\min(N,\max(1,R_z\oplus y))$ とし、$l'=\min(u,v),r'=\max(u,v),L'=\min(U,V),R'=\max(U,V)$ とする。
  • $z \bmod 2=0$ のとき、 $A$ の区間 $[l',r']$ のそれぞれの値を $x_z \oplus y$ と論理和をとったもので置き換える。
  • $z \bmod 2=1$ のとき、 $A$ の区間 $[l',r']$ のそれぞれの値を $x_z \oplus y$ と論理積をとったもので置き換える。
  • $y$ を $A$ の区間 $[L',R']$ の和を $2^{30}$ で割ったあまりで置き換える。

• 最終的な $y$ の値を出力してください。

ここで、 $X \oplus Y$ は $X$ と $Y$ の排他的論理和を表します。

入力

入力は以下の形式で標準入力から与えられます。

$N\ M$
$A_1\ A_2\ \ldots\ A_N$
$l_1\ l_2\ \ldots\ l_M$
$r_1\ r_2\ \ldots\ r_M$
$x_1\ x_2\ \ldots\ x_M$
$L_1\ L_2\ \ldots\ L_M$
$R_1\ R_2\ \ldots\ R_M$
$Q$
$\text{problem}_1$
$\text{problem}_2$
$\vdots$
$\text{problem}_Q$

$\text{problem}_i$ は $i$ 個目の小問題を表し、以下の形式で与えられます。

$s_i\ q_i$

• $1\leq N,M,Q\leq 10^5$
• $0\leq A_i, x_i < 2^{30}$
• $1\leq l_i,r_i,L_i,R_i\leq N$
• $1\leq s_i\leq M$
• $1\leq q_i\leq 10^3$
• $1\leq \sum_{i=1}^{Q} q_i\leq 10^6$
• 入力はすべて整数

出力

$Q$ 行出力してください。 $i$ 行目には、小問題 $i$ の答えを出力してください。 最後に改行してください。

サンプル

10 8
3 5 8 13 21 34 55 89 144 233
1 2 4 6 8 10 3 5
5 9 7 1 10 4 8 2
7 15 31 63 127 255 511 1023
1 3 5 7 9 2 4 6
10 8 6 4 2 9 7 1
6
1 5
3 6
5 4
8 7
2 8
6 5

0
3274
1007
1023
992
127