Alice and Bob’s Bitwise XOR Game

Alice and Bob are playing a turn‐based game. Initially, there is an integer x and a multiset \(a\) of non‑negative integers. Every element in a is either 0 or of the form \(2^i\) for some \(0\le i<k\). In fact, for each \(i\) from 0 to \(k-1\) there are exactly \(b_i\) copies of \(2^i\) in a, and there are also z copies of 0.

The game proceeds as follows. Alice moves first, and then the players alternate. On a turn, the current player picks any number p from the multiset \(a\) and then decides whether or not to update x by doing \(x \gets x \oplus p\) (where \(\oplus\) denotes the bitwise XOR), after which p is removed from \(a\>.

Alice aims to maximize the final value of \(x\), while Bob wants to minimize it. Both players are optimal, and they can choose the order in which to remove the tokens. Note that removing a 0 (or choosing not to modify x) has no immediate effect but may be used to postpone an unfavorable move. In essence, the copies of 0 allow a player to "pass" if they do not wish to change x.

Observation and Analysis:

Since every nonzero element is a power of two, each move that involves a nonzero token affects exactly one bit of x. Moreover, note that in any turn the player may decide not to use the effect of a nonzero token, effectively keeping x unchanged. Thus, the players can use the 0‐tokens to postpone playing tokens that would adversely affect their goal.

The key observation is that as long as there is at least one 0-token available, a player can always choose that token and avoid disturbing x. Hence, the crucial moment comes when all 0-tokens are exhausted. At that point, only nonzero tokens remain, and moves become forced. Let the total number of 0’s be \(z\). After \(z\) moves (with both players choosing 0’s), the turn order in the forced phase is determined by the parity of \(z\):

• If \(z\) is even, then Alice will start the forced phase.
• If \(z\) is odd, then Bob will start the forced phase.

When only nonzero tokens remain, consider each bit position \(i\) (with \(i=0,1,\dots,k-1\)). There are \(b_i\) tokens of \(2^i\). Because each token can be "activated" (i.e. used to XOR x) or not—and players can cancel out the effect of pairs of tokens—the final effect on the \(i\)th bit depends only on the parity of \(b_i\).

In the forced phase, the starting player will choose to apply the XOR of a token if and only if it improves the final outcome from his/her perspective. Since XORing \(2^i\) toggles the \(i\)th bit, the optimal decisions lead to the following conclusion for each bit \(i\):

• If the forced phase is started by Alice (i.e. \(z\) is even):
  • If \(b_i\) is even, the two players can cancel out each other’s moves and the \(i\)th bit remains as in x.
  • If \(b_i\) is odd, then no matter what the initial \(i\)th bit was, Alice can force it to 1 by applying an extra flip if needed. (If x already has a 1 in the \(i\)th bit, she simply does nothing.)
• If the forced phase is started by Bob (i.e. \(z\) is odd):
  • If \(b_i\) is even, the final \(i\)th bit remains unchanged.
  • If \(b_i\) is odd, then Bob can force the \(i\)th bit to 0. (If x already has a 0 in that bit, he does nothing.)

Thus, the final \(i\)th bit, denoted as \(f(i)\), can be determined as follows:

If \(z\) is even (Alice starts forced phase): \[ f(i)= \begin{cases} 1, & \text{if } x_i=1 \text{ or } (b_i \bmod 2=1),\\[6mm] 0, & \text{otherwise.} \end{cases} \]

If \(z\) is odd (Bob starts forced phase): \[ f(i)= \begin{cases} 1, & \text{if } x_i=1 \text{ and } (b_i \bmod 2=0),\\[6mm] 0, & \text{otherwise.} \end{cases} \]

The final value of x is then \[ x_{final} = \sum_{i=0}^{k-1} f(i) \cdot 2^i. \]

Your task is to compute \(x_{final}\) given \(x\), \(k\), the counts \(b_0, b_1, \dots, b_{k-1}\) and z.

inputFormat

The input consists of three lines:

• The first line contains two integers: k (the number of bit positions) and x (the initial value of x).
• The second line contains k non-negative integers: b0 b1 ... b(k-1), where bi is the number of tokens with value \(2^i\).
• The third line contains a non-negative integer z, the number of zeros in the multiset.

Note that 0 ≤ x, bi, z. You may assume that k is small (for example, k ≤ 60).

outputFormat

Output a single integer: the final value of x after all tokens are removed assuming optimal play by both players.

sample

3 0
1 0 0
0

1