Merkle–Hellman 背包加密系统是 Ralph Merkle 和 Martin Hellman 于 1978 年发明的最早的公钥加密系统之一。以下是其描述。

Alice 选择 $n$ 个正整数 $\{a_1, \dots, a_n\}$，使得每个 $a_i > \sum_{j=1}^{i-1} a_j$，选择一个大于所有 $a_i$ 之和的正整数 $q$，以及一个与 $q$ 互质的正整数 $r$。这 $n+2$ 个整数是 Alice 的私钥。

然后 Alice 计算 $b_i = (a_i \cdot r) \pmod q$。这 $n$ 个整数是 Alice 的公钥。

在知道公钥的情况下，Bob 可以向 Alice 传输一个 $n$ 位的消息。为此，他计算 $s$，即消息中第 $i$ 位为 1 的所有 $b_i$ 之和。这个值 $s$ 就是加密后的消息。

请注意，窃听者 Eve 在已知加密消息和公钥的情况下，必须解决一个（通常被认为是困难的）背包问题实例才能找到原始消息。与此同时，Alice 在收到 $s$ 后，可以在线性时间内计算出原始消息；我们将其留作练习。

在本题中，你将处理 Merkle–Hellman 背包加密系统的一种实现，其中 Alice 出于明显的性能原因选择了 $q = 2^{64}$，并公布了这一信息。由于每个人都知道她的 $q$，为了通信简便，她要求 Bob 发送计算出的 $s$ 对 $2^{64}$ 取模后的值。

你需要破解这一实现。给定公钥和加密消息，还原出原始消息。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 64$)。 接下来的 $n$ 行，每行包含一个整数 $b_i$ ($1 \le b_i < 2^{64}$)。 最后一行包含一个整数 $s \pmod q$ —— 即加密消息 $s$ 对 $q$ 取模后的值 ($0 \le s \pmod q < 2^{64}$)。

给定的序列 $b_i$ 是该实现中有效的公钥，给定的值 $s \pmod q$ 是有效的加密消息。

输出格式

输出恰好 $n$ 位（0 或 1）—— 即原始消息。

样例

输入 1

5
10
20
50
140
420
440

输出 1

01001