Shift Register

A register of a computer stores N bits for computation. A shift register is a special kind of register, with bit values that can be easily shifted by one position.

Using a feedback shift register, binary pseudo-random numbers can be generated in the following way: A shift register of size N is initially filled with the bit values a₁,a₂,...,a_N. At each clock tick, the register outputs the value of the rightmost bit, a_N. The other bit values are shifted by one position to the right. The first position is assigned a new value a'₁ as follows:

Each bit of the register is connected to an XOR gate via a switch (see figure below). For each bit i there is a switch s_i (which can be 1 or 0) that determines whether the bit value a_i is forwarded or not to the XOR gate. Let k_i = s_i * a_i. The new value a'₁ is set to the output value of the XOR gate, XOR(k₁,...,k_N). (Remark: If the number of ones in k₁,... k_N is odd, the value of XOR(k₁,...,k_N) is 1, else 0). Below are the formal definitions:

a'₁ = XOR(k₁, ..., k_N)
a'_i = a_{i-1} for 2 �� i �� N
output = a_N

tick a1 a2 a3 a4 a5 a6 a7 output 0 1 0 1 1 0 0 1 - 1 0 1 0 1 1 0 0 1 2 1 0 1 0 1 1 0 0 3 1 1 0 1 0 1 1 0 4 0 1 1 0 1 0 1 1 5 0 0 1 1 0 1 0 1 6 1 0 0 1 1 0 1 0 7 1 1 0 0 1 1 0 1 8 0 1 1 0 0 1 1 0 9 1 0 1 1 0 0 1 1 10 0 1 0 1 1 0 0 1 11 1 0 1 0 1 1 0 0 12 1 1 0 1 0 1 1 0 13 0 1 1 0 1 0 1 1 14 0 0 1 1 0 1 0 1

In the example above, the value a₁ at tick 1 is calculated as follows:

XOR(1 * 1, 0 * 0, 1 * 1, 1 * 1, 0 * 0, 1 * 0, 1 * 1) = 0.

You are given the first 2N output values of such a feedback shift register. From those values, you shall try to determine the switch values s_i.

Input

The first line of the input file register.in contains the size N of the shift register (1 �� N �� 750). The second line contains 2N numbers 0 or 1, which are the first 2N output bit values of the shift register.

Output

The output file register.out consists of exactly one line. If there is a switch setting that produces the given register output values, output the switch values s_i of any such switch setting, starting with s₁. If there are no such switch settings, output the number -1 only.

Example