문제

The Merkle–Hellman Knapsack Cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978. Here is its description.

Alice chooses $n$ positive integers $\{a_1, \ldots, a_n\}$ such that each $a_i > \sum_{j=1}^{i-1} a_j$, a positive integer $q$ which is greater than the sum of all $a_i$, and a positive integer $r$ which is coprime with $q$. These $n+2$ integers are Alice's private key.

Then Alice calculates $b_i = (a_i \cdot r) \bmod q$. These $n$ integers are Alice's public key.

Knowing her public key, Bob can transmit a message of $n$ bits to Alice. To do that he calculates $s$, the sum of $b_i$ with indices $i$ such that his message has bit $1$ in $i$-th position. This value $s$ is the encrypted message.

Note that an eavesdropper Eve, who knows the encrypted message and the public key, has to solve a (presumably hard) instance of the knapsack problem to find the original message. Meanwhile, after receiving $s$, Alice can calculate the original message in linear time; we leave it to you as an exercise.

In this problem you deal with the implementation of the Merkle–Hellman Knapsack Cryptosystem in which Alice chose $q=2^{64}$, for obvious performance reasons, and published this information. Since everyone knows her $q$, she asks Bob to send her the calculated value $s$ taken modulo $2^{64}$ for simplicity of communication.

You are to break this implementation. Given the public key and an encrypted message, restore the original message.

입력

The first line contains one integer $n$ ($1 \le n \le 64$).

Each of the next $n$ lines contains one integer $b_i$ ($1 \le b_i < 2^{64}$).

The last line contains one integer $s \bmod q$ — the encrypted message $s$ taken modulo $q$ ($0 \le s \bmod q < 2^{64}$).

The given sequence $b_i$ is a valid public key in the described implementation, and the given value $s \bmod q$ is a valid encrypted message.

출력

Output exactly $n$ bits (0 or 1 digits) — the original message.

예제 입력 1

5
10
20
50
140
420
440

예제 출력 1

01001