Description

A computer register stores $N$ bits used for computations. A shift register is a special type of register whose bit values can be shifted by one position easily.

Using a feedback shift register, binary pseudo-random numbers can be generated as follows:

• A shift register of size $N$ is initially filled with bit values $a_1,a_2,\cdots,a_N$.
• Each time, the register outputs the value of its rightmost bit $a_N$. All other bit values shift one position to the right. The first position is assigned a new value $a_1^{\prime}$, as described below:
  • Each bit of the register is connected to an XOR gate through a switch (see the figure below). For each bit $i$, there is a switch $s_i$ (either $1$ or $0$) that decides whether the bit value $a_i$ is forwarded to the XOR gate.
  • Let $k_i=s_i\cdot a_i$. The new value $a_1^{\prime}$ is set to the output of the XOR gate, i.e., $\text{XOR}(k_1,\cdots, k_N)$.
• Note: If the number of $1$'s among $k_1,\cdots,k_N$ is odd, then $\text{XOR}(k_1,\cdots,k_N)=1$, otherwise it is $0$. The formal definition is:

In the example above, the first value $a_1^{\prime}$ is computed as follows: $\text{XOR}(1\cdot 1,0\cdot 0,1\cdot 1,1\cdot 1,0\cdot 0,1\cdot 0,1\cdot 1)=0$.

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

Input Format

The first line contains an integer $N$, the size of the shift register.

The second line contains $2N$ digits 0 or 1, representing the first $2N$ output bit values of the register.

Output Format

The output contains only one line.

• If there exists at least one switch setting that produces the given register output values, output a line of $N$ integers, where the $i$-th integer is the value of switch $s_i$. Any such switch setting will be accepted.
• If no such switch setting exists, output -1.

7
1 0 0 1 1 0 1 0 1 1 0 0 1 1

1 0 1 1 0 1 1

3
0 0 0 1 1 1

-1

Hint

Constraints

For $100\%$ of the testdata, $1\le N\le 750$.

Notes

This problem comes from Shift Register of the CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2003.

Translated and organized by @求学的企鹅.

Translated by ChatGPT 5