시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 63 16 6 12.245%

## 문제

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 {a1, . . . , an} such that each ai > Σi−1j=1aj, a positive integer q which is greater than the sum of all ai, and a positive integer r which is coprime with q. These n + 2 integers are Alice’s private key.

Then Alice calculates bi = (ai · r) mod 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 bi 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 = 264, 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 264 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 ≤ n ≤ 64).

Each of the next n lines contains one integer bi (1 ≤ bi < 264).

The last line contains one integer s mod q — the encrypted message s taken modulo q (0 ≤ s mod q < 264).

The given sequence bi is a valid public key in the described implementation, and the given value s mod 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