Breaking the Merkle-Hellman Knapsack Cryptosystem

The Merkle-Hellman Knapsack Cryptosystem was one of the earliest public key cryptosystems. In this problem, you are given the public key and an encrypted message computed modulo \(2^{64}\). The public key consists of \(n\) integers \(b_i\), which were generated from a super‐increasing sequence \(a_i\) by the formula

\(b_i = (a_i \cdot r) \bmod 2^{64}\),

for some secret odd integer \(r\) (which has an inverse \(r^{-1}\) modulo \(2^{64}\)).

The decryption works as follows. There exists a unique odd integer \(k = r^{-1}\) such that when you compute

\(a_i = (b_i \cdot k) \bmod 2^{64}\),

the sequence \(a_1, a_2, \dots, a_n\) becomes super‐increasing, i.e. for each \(i \ge 2\),

\(a_i > \sum_{j=1}^{i-1}a_j\).

After finding \(k\), compute

\(s' = (s \cdot k) \bmod 2^{64}\),

where \(s\) is the encrypted message. Then, the original \(n\)-bit message \(x_1x_2\ldots x_n\) is recovered using the following greedy algorithm: for \(i = n, n-1, \dots, 1\), if \(s' \ge a_i\) then set \(x_i = 1\) and update \(s' = s' - a_i\); otherwise set \(x_i = 0\>.

inputFormat

The input consists of three lines:

• The first line contains an integer \(n\) (the length of the public key).
• The second line contains \(n\) space-separated unsigned 64-bit integers representing the public key \(b_1, b_2, \dots, b_n\) in the order corresponding to the private key.
• The third line contains the encrypted message \(s\) as an unsigned 64-bit integer.

outputFormat

Output the original \(n\)-bit message as a string of \(0\)s and \(1\)s.

sample

4
11 21 51 131
99

1010