Little S wants to hold an arena game. If there are $2^k$ participants, the game proceeds in $k$ rounds: In the first round, participants with IDs $1, 2$ play a match, participants with IDs $3, 4$ play a match, and so on, with participants $2^k - 1, 2^k$ playing a match. In the second round, the winners of the first round play against each other in adjacent pairs. Similarly, in the $(k-1)$-th round, the 4 winners from the $(k-2)$-th round play, with the first two and the last two playing against each other, which is the semi-final. The $k$-th round is the final between the two semi-final winners.

After determining the rules for advancing, Little S sets the rules for the arena matches. Specifically, each participant has an ability value $a_1, a_2, \dots, a_{2^k}$, where the ability values are in the range $[0, 2^{31} - 1]$. For each match, a draw is made to determine a $0/1$ value. Let $d_{R,G}$ denote the draw for the $G$-th match of the $R$-th round. A draw of $0$ means the participant with the smaller ID is the "host," and a draw of $1$ means the participant with the larger ID is the "host." The host wins if and only if their ability value $a \ge R$. In other words, the outcome of the game depends only on the host's ability value and the current round number, and is independent of the other participant's ability value.

Now, Little S receives the registration information of $n$ participants one after another, and they tell Little S their ability values. Little S assigns IDs $1, 2, \dots, n$ to the participants in the order they registered. Little S is interested in the sum of the IDs of all participants who could potentially be the champion after supplementing the minimum number of participants to make the total a power of 2 and having all participants play a complete arena game.

Formally, let $k$ be the smallest non-negative integer such that $2^k \ge n$. Then $2^k - n$ participants are supplemented, and the ability values of the supplemented participants can be any value in $[0, 2^{31} - 1]$. If a supplemented participant can win, they should also be included in the answer.

Little S thinks this problem is too simple, so he gives you $m$ queries $c_1, c_2, \dots, c_m$. Little S wants you to find the answer to this problem for each $c_i$ when only the registration information of the first $c_i$ participants is received.

Input

Read from the file arena.in.

The test cases for this problem contain multiple test sets, but different test sets are obtained only by modifying $a_1, a_2, \dots, a_n$, while other content remains unchanged. Please refer to the format below. Here $\oplus$ represents the XOR operator, and $a \pmod b$ represents the remainder of $a$ divided by $b$.

The first line contains two positive integers $n, m$, representing the number of participants and the number of queries. The second line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$, which will be used to calculate the true ability values. The third line contains $m$ positive integers $c_1, c_2, \dots, c_m$, representing the queries. Let $K$ be the smallest non-negative integer such that $2^K \ge n$. In the following $K$ lines, the $R$-th line contains $2^{K-R}$ integers (separated by spaces), where the $G$-th integer represents the draw $d_{R,G} = 0/1$ for the $G$-th match of the $R$-th round.

Note: Since the queries only require filling the number of people up to $2^k \ge c_i$, where $k \le K$, you may not use all the input values.

The next line contains a positive integer $T$, representing $T$ test sets. The following $T$ lines each describe a test set, containing 4 non-negative integers $X_0, X_1, X_2, X_3$. The ability values for this test set are $a_i = a'_i \oplus X_{i \pmod 4}$, where $1 \le i \le n$.

Output

Output to the file arena.out.

Output $T$ lines in total. For each test set, let $A_i$ be the answer to the $i$-th ($1 \le i \le m$) query. You only need to output one line containing an integer representing the result of $(1 \times A_1) \oplus (2 \times A_2) \oplus \dots \oplus (m \times A_m)$.

Constraints

For all test cases, it is guaranteed that: $2 \le n, m \le 10^5$, $0 \le a_i, X_j < 2^{31}$, $1 \le c_i \le n$, $1 \le T \le 256$.

Special Property A: It is guaranteed that all $c_i$ are powers of 2. Special Property B: It is guaranteed that all $d_{R,G} = 0$.