Knapsack Cryptosystem

The Merkle-Hellman knapsack cryptosystem is one of the first public key cryptosystems. Ralph Merkle and Martin Hellman published it in 1978. It works like this.

Alice picks $n$ positive integers $a_1, \dots, a_n$ such that $a_i > \sum_{j=1}^{i-1} a_j$ holds for every $i$, a positive integer $q$ greater than $a_1 + \dots + a_n$, and a positive integer $r$ coprime with $q$. These $n + 2$ integers are Alice's private key.

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

Knowing the public key, Bob can send Alice a message of $n$ bits. He computes $s$, the sum of the $b_i$ over the indices $i$ where his message has bit 1. The value $s$ is the encrypted message.

An eavesdropper Eve, who knows the public key and the encrypted message, has to solve an instance of the knapsack problem, which is presumably hard. Alice, on the other hand, recovers the message in linear time once she receives $s$.

This problem is about an implementation in which Alice chose $q = 2^{64}$ for obvious performance reasons and published that choice. Since everyone knows her $q$, she asks Bob to send the value $s$ taken modulo $2^{64}$, which keeps the communication simple.

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 $s \bmod q$, the encrypted message taken modulo $q$ ($0 \le s \bmod q < 2^{64}$).

The given sequence $b_1, \dots, b_n$ is a valid public key of the implementation above, and the given value is a valid encrypted message.

Print exactly $n$ characters on one line, each of them 0 or 1, the bits of the original message in order.

Exactly one message fits the input, because the subset sums of $a_1, \dots, a_n$ are pairwise different.