Person in Charge

• SleepingCup

Problem Description

Little S wants to organize a tournament game. If there are $2^k$ participants, the game will proceed in $k$ rounds:

• In the first round, participants with IDs $1$ and $2$ compete, participants with IDs $3$ and $4$ compete, and so on, up to participants with IDs $2^k - 1$ and $2^k$.
• In the second round, only the winners from the first round remain, and adjacent pairs compete sequentially.
• This continues similarly until the $(k - 1)$-th round, where only the $4$ winners from the $(k - 2)$-th round remain, and the first two and last two compete separately (i.e., the semifinals).
• The $k$-th round is the final between the two winners of the semifinals.

After determining the advancement rules, Little S sets the match rules as a "challenge" system. Specifically, each participant has an ability value $a_1, a_2, \dots, a_{2^k}$, where each $a_i$ is an integer in $[0, 2^{31}-1]$. For each match, a number $0$ or $1$ is drawn randomly. Let $d_{R,G}$ denote the number drawn for the $G$-th match in the $R$-th round. If $d_{R,G} = 0$, the participant with the smaller ID is the "challenger"; if $d_{R,G} = 1$, the participant with the larger ID is the challenger. The challenger wins if and only if their ability value $a \ge R$. In other words, the outcome of the match depends solely on the challenger's ability value and the current round number, and is independent of the other participant's ability value.

Now, Little S receives registration information from $n$ participants one by one, each reporting their ability value. Little S assigns IDs $1, 2, \dots, n$ to the participants in the order they register. Little S is interested in determining the minimum number of additional participants needed to make the total number of participants a power of $2$, and the sum of IDs of all possible champions after a complete tournament under all possible outcomes.

Formally, let $k$ be the smallest non-negative integer such that $2^k \ge n$. Then, $(2^k - n)$ additional participants must be added, and their ability values can be any integers in $[0, 2^{31}-1]$. If an additional participant has a chance to win, their ID must also be included in the answer.

Little S finds this problem too simple, so he gives you $m$ queries $c_1, c_2, \dots, c_m$. For each $c_i$, Little S asks you to compute the answer when only the first $c_i$ participants have registered.

Input Format

This problem contains multiple test cases. However, different test cases are generated by modifying only $a_1, a_2, \dots, a_n$, while other content remains unchanged. Refer to the following format. Here, $\oplus$ denotes the bitwise XOR operator, and $a \bmod b$ denotes the remainder when $a$ is divided by $b$.

The first line of input contains two positive integers $n, m$, representing the number of registered participants and the number of queries.

The second line contains $n$ non-negative integers $a'_1, a'_2, \dots, a'_n$, which are used to compute the actual 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$. The next $K$ lines each contain $2^{K-R}$ numbers (without spaces), where the $G$-th number in the $R$-th line represents the drawn value $d_{R,G} = 0/1$ for the $G$-th match in the $R$-th round.

Note that since queries only require rounding the number of participants 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$, indicating the number of test cases.

The following $T$ lines each describe a test case with $4$ non-negative integers $X_0, X_1, X_2, X_3$. The actual ability values for the test case are computed as $a_i = a'_i \oplus X_{i \bmod 4}$, where $1 \le i \le n$.

Output Format

Output $T$ lines. For each test case, let $A_i$ be the answer for the $i$-th query ($1 \le i \le m$). You need to output a single integer per line, representing $(1 \times A_1) \oplus (2 \times A_2) \oplus \dots \oplus (m \times A_m)$.

Samples

5 5
0 0 0 0 0
5 4 1 2 3
1001
10
1
4
2 1 0 0
1 2 1 0
0 2 3 1
2 2 0 1

5
19
7
1

Sample 1 Explanation

There are $T = 4$ test cases. Here, only the first test case is explained. The actual ability values for the $5$ participants are $[1, 0, 0, 2, 1]$. The $5$ queries are for prefixes of lengths $5, 4, 1, 2, 3$.

1. For the prefix of length $1$, since there is only participant $1$, the answer is $1$.
2. For the prefix of length $2$, since $2$ is already a power of $2$, no additional participants are needed. The draw $d_{1,1} = 1$ means participant $2$ is the challenger. Since $a_2 < 1$, participant $1$ wins, and the answer is $1$.
3. For the prefix of length $3$, participant $1$ wins against $2$ (since $d_{1,1} = 1$, $2$ is the challenger, and $a_2 < 1$). Although the ability value of participant $4$ is unknown, participant $4$ will always win against $3$ (since $d_{1,2} = 0$, $3$ is the challenger, and $a_3 < 1$). In the final, either $1$ or $4$ can win (since $d_{2,1} = 1$, $4$ is the challenger; if $a_4 < 2$, $1$ wins; otherwise, $4$ wins). Thus, the answer is $1 + 4 = 5$.
4. For the prefix of length $4$, since $a_4 \ge 2$, participant $4$ wins the final.
5. For the prefix of length $5$, it can be shown that possible winners include participants $4$, $7$, and $8$, so the answer is $19$.

Thus, the output for this test case is $(1 \times 19) \oplus (2 \times 4) \oplus (3 \times 1) \oplus (4 \times 1) \oplus (5 \times 5) = 5$.

Sample 2

See the files arena/arena2.in and arena/arena2.ans in the contestant directory.

This sample satisfies Special Property A.

Sample 3

See the files arena/arena3.in and arena/arena3.ans in the contestant directory.

This sample satisfies Special Property B.

Sample 4

See the files arena/arena4.in and arena/arena4.ans in the contestant directory.

Sample 5

See the files arena/arena5.in and arena/arena5.ans in the contestant directory.

Data Range

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: All queries $c_i$ are powers of $2$.

Special Property B: All $d_{R,G} = 0$.