Shift Register

A register stores $N$ bits used for computation. A shift register is a special kind of register in which every stored bit can be shifted one position.

A shift register can produce a binary pseudo-random sequence as follows. A shift register of size $N$ holds the bits $a_1, a_2, \ldots, a_N$. On every clock tick the register outputs its rightmost bit $a_N$, and every other bit moves one position to the right. The now-empty first position $a'_1$ is filled as described below.

Each bit of the register is connected through a switch to a single XOR gate, as shown in the figure. Each bit $i$ has a switch $s_i \in {0, 1}$ that decides whether its bit $a_i$ is fed into the XOR gate ($s_i = 1$) or not ($s_i = 0$). Let $k_i = s_i \cdot a_i$; then $a'_1$ equals the XOR-gate output $\mathrm{XOR}(k_1, \ldots, k_N)$. That is, it is 1 if the number of ones among $k_1, \ldots, k_N$ is odd, and 0 otherwise.

• $a'_1 = \mathrm{XOR}(k_1, \ldots, k_N)$
• $a'i = a{i-1}$ for $2 \le i \le N$
• output $= a_N$

For example, in the state shown above the bit newly filled in on the first tick is $\mathrm{XOR}(1 \cdot 1, 0 \cdot 0, 1 \cdot 1, 1 \cdot 1, 0 \cdot 0, 1 \cdot 0, 1 \cdot 1) = 0$.

The first $2N$ values of the sequence produced by the shift register are given. Write a program that recovers the switch values $s_1, \ldots, s_N$.

The first line contains the size $N$ of the shift register ($1 \le N \le 750$).

The second line contains the first $2N$ values output by the shift register, separated by spaces; each value is 0 or 1.

If a switch setting that reproduces the given output sequence exists, print the lexicographically smallest such setting: the values $s_1, s_2, \ldots, s_N$ separated by spaces on a single line. Among all valid settings, compare them entry by entry starting from $s_1$ and prefer the one that has 0 rather than 1 at the first position where they differ. If no setting can produce the given output, print -1.