P7693 [CEOI 2003] Shift Register

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: $$a_1^{\prime}=XOR(k_1,\cdots,k_N)$$ $$a_i^{\prime}=a_{i−1}\ \text{for}\ 2\le i\le N$$ $$\text{output}=a_N$$  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$.

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.

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`.

#### Constraints For $100\%$ of the testdata, $1\le N\le 750$. #### Notes This problem comes from [Shift Register](https://www.ceoi2003.de/www/downloads/register-en.ps) of the CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2003. Translated and organized by @[求学的企鹅](/user/271784). Translated by ChatGPT 5