The Content Scramble System (CSS) is a method used to encrypt content on DVD media so that only licensed devices can access it. In the variant of this system we are dealing with, the key $K$ is a sequence of exactly 42 bits $k_1, k_2, \dots, k_{42}$, while the content is a sequence of $n$ bytes. The content is encrypted by first generating a so-called key stream $T(K)$—also a sequence of $n$ bytes—based on the key, and then applying the bitwise exclusive OR operation to the corresponding elements of the content and the key stream.

If the encrypted text and some bytes of the content are known, we can determine the corresponding bytes of the key stream. Your task is to determine one possible key $K$ based on a partially known key stream $T(K)$.

The function $T(K)$ that generates the key stream is based on a logic circuit called a Linear-feedback shift register (LFSR). The state of an LFSR consists of $m$ bits $b_1, b_2, \dots, b_m$, and its functionality is defined by a set of feedback positions. In one cycle, the LFSR generates one output bit and changes its state as follows:

1. The output bit $b$ is calculated by summing the bits at the feedback positions. If the result is even, then $b$ is 0, otherwise it is 1. Thus, $b$ is the exclusive OR of the bits at the feedback positions.
2. All state bits are shifted to the left, bit $b_1$ is discarded, and bit $b$ is placed in the last position. Thus, the new state is $b_2, b_3, \dots, b_m, b$.

One step of the LFSR consists of 8 cycles, and the result is one byte formed by the output bits of the cycles in order from right to left. Specifically, if the output bits of the cycles are $i_1, i_2, \dots, i_8$, then the result of the step is the integer between 0 and 255 whose binary representation is $(i_8 i_7 \dots i_1)_2$.

CSS uses two such circuits: LFSR17 of size 17 bits, in which positions 1 and 15 are marked as feedback, and the initial state consists of the bits of the key $k_1, k_2, \dots, k_{17}$ in order. LFSR25 of size 25 bits, in which positions 1, 4, 5, and 13 are marked as feedback, and the initial state consists of the bits of the key $k_{18}, k_{19}, \dots, k_{42}$ in order.

The key stream $T(K)$ is generated as follows: 1. The LFSR17 and LFSR25 circuits are set to their initial states using the key $K$ as described. 2. The value of the variable $c$ is set to 0. 3. Repeat $n$ times: (a) Perform one step of the LFSR17 circuit, let $x$ be the result of the step. (b) Perform one step of the LFSR25 circuit, let $y$ be the result of the step. (c) Calculate the sum $z = x + y + c$. (d) If $z \ge 256$, $z$ is decreased by 256, and $c$ is set to 1. Otherwise, $c$ is set to 0. (e) The next byte of the key stream is exactly $z$.

You are given a key stream in which some bytes are known and some are unknown. Determine one possible key $K$ from which a stream matching the given one can be obtained in the described manner.

Input

The first line contains a natural number $n$, the length of the given key stream. The next line contains $n$ integers $t_1, t_2, \dots, t_n$ – the bytes of the key stream in order. If the $k$-th byte is unknown, $t_k = -1$, and if it is known, $0 \le t_k \le 255$.

Output

In the first line, print the bits of the required key $k_1, k_2, \dots, k_{42}$ without spaces.

Note

A solution will always exist, although it does not have to be unique.

Examples

Input 1

7
154 39 225 99 151 145 -1

Output 1

011000110010100101100110000000000000111011