Story

?? "Problems with a tight Memory Limit are garbage problems."

Problem Statement

You are given an integer sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$. You are also given integer sequences $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)$ of length $M$.

Process the following $Q$ subproblems $i=1,2,\ldots, Q$ in order. Note that the values of $A$ are independent for each subproblem.

<Subproblem $i$>

• You are given integers $s_i, q_i$. Initially, let $y=i$. Process the following $q_i$ queries $j=1,2,\ldots,q_i$ in order.

  <Query $j$>

  • Let $z=((s_i+j) \bmod M)+1$.
  • Also, let $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))$, and let $l'=\min(u,v),r'=\max(u,v),L'=\min(U,V),R'=\max(U,V)$.
  • If $z \bmod 2=0$, replace each value in the interval $[l',r']$ of $A$ with its bitwise OR with $x_z \oplus y$.
  • If $z \bmod 2=1$, replace each value in the interval $[l',r']$ of $A$ with its bitwise AND with $x_z \oplus y$.
  • Replace $y$ with the sum of the interval $[L',R']$ of $A$ modulo $2^{30}$.

• Output the final value of $y$.

Here, $X \oplus Y$ denotes the bitwise XOR of $X$ and $Y$.

Input

The input is given from standard input in the following format.

$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$ represents the $i$-th subproblem and is given in the following format.

$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$
• All input values are integers.

Output

Output $Q$ lines. On the $i$-th line, output the answer to subproblem $i$. End the output with a newline.

Sample

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