Hidden Number

Let $L$ be the length of the binary representation of a positive integer $N$.

You are given a bit string $P=(P_1,P_2,\cdots,P_L)$ of length $L$. For each $P_i$, there exists a positive integer $r_i$ such that $P_i \equiv r_i \pmod 2$.

For a positive integer $x$, consider the following process.

• Initially, create the sequence $A=(1,2,\cdots,2x)$.
• While the length of $A$ is greater than $1$, repeat the following operation.
  • Choose two different positions in the current sequence, and let their values be $a,b$.
  • Remove the two chosen elements and append $|a-b|$ to the end of the sequence.
• Let $f(x)$ be the last remaining element.

The choices of the two elements are arbitrary. The parity of $f(x)$ used in this problem is guaranteed to be independent of those choices.

Define a bit string $K=(K_1,K_2,\cdots,K_L)$ of length $L$ as follows.

Let $K$ be the integer represented by this binary string, where $K_1$ is the most significant bit and $K_L$ is the least significant bit. The integer $C$ satisfies

where $\oplus$ denotes the bitwise XOR operation.

Given the bit string $P$ and the integer $C$, find the original integer $N$.

The input is given in the following format.

$L$ $P_1\ P_2\ \cdots\ P_L$ $C$

Print the original integer $N$ on the first line.

• $2 \leq L \leq 30$.
• $P_i \in \{0,1\}$ ($1 \leq i \leq L$).
• $0 \leq C \leq 2^{30}-1$.
• The input is given so that there exists an original integer $N$ such that $2 \leq N \leq 2^{30}-1$ and the binary representation of $N$ has length $L$.