숨겨진 수

어떤 양의 정수 $N$의 이진 표현의 길이를 $L$이라 하자.

길이가 $L$인 비트열 $P=(P_1,P_2,\cdots,P_L)$이 주어진다. 각 $P_i$는 어떤 양의 정수 $r_i$에 대하여 $P_i \equiv r_i \pmod 2$를 만족한다.

양의 정수 $x$에 대하여 다음 과정을 생각하자.

• 처음 수열 $A=(1,2,\cdots,2x)$를 만든다.
• 수열 $A$의 길이가 $1$이 될 때까지 다음 연산을 반복한다.
  • 현재 수열에서 서로 다른 두 위치를 고르고, 그 위치의 값을 각각 $a,b$라 하자.
  • 고른 두 원소를 제거하고, $|a-b|$를 수열의 뒤에 추가한다.
• 마지막으로 남은 원소를 $f(x)$라 하자.

두 원소를 고르는 방법은 임의이다. 이 문제에서 사용하는 $f(x)$의 홀짝성은 두 원소를 고르는 방법과 관계없이 동일함이 보장된다.

길이가 $L$인 비트열 $K=(K_1,K_2,\cdots,K_L)$을 다음과 같이 정의한다.

또한 $K_1$을 최상위 비트, $K_L$을 최하위 비트로 하는 이진수를 정수 $K$라 하자. 정수 $C$는

를 만족한다. 여기서 $\oplus$는 비트 단위 XOR 연산이다.

비트열 $P$와 정수 $C$가 주어질 때, 원래의 정수 $N$을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

첫째 줄에 원래의 정수 $N$을 출력한다.

• $2 \leq L \leq 30$.
• $P_i \in \{0,1\}$ ($1 \leq i \leq L$).
• $0 \leq C \leq 2^{30}-1$.
• 입력은 $2 \leq N \leq 2^{30}-1$이고 $N$의 이진 표현의 길이가 $L$인 원래의 정수 $N$이 존재하도록 주어진다.