题目描述

计算机的寄存器存储 $N$ 位用于计算。移位寄存器是一种特殊的寄存器，其位值可以很容易地移位一位。

使用反馈移位寄存器，可以通过以下方式生成二进制伪随机数：

• 大小为 $N$ 的移位寄存器最初填充位值 $a_1,a_2,\cdots,a_N$。
• 每次，寄存器输出其最右边位的值 $a_N$。其他位值向右移动一个位置。第一个位置被分配一个新值 $a_1^{\prime}$，如下所示：
  • 寄存器的每一位都通过一个开关连接到一个异或门（见下图）。对于每个位 $i$，有一个开关 $s_i$（可以是 $1$ 或 $0$），用于确定位值 $a_i$ 是否被转发到 XOR 门。
  • 令 $k_i=s_i\cdot a_i$。新值 $a_1^{\prime}$ 被设置为 XOR 门的输出值 XOR（$k_1,\cdots, k_N$）。
• 注：如果 $k_1,\cdots,k_N$ 中 $1$ 的个数为奇数，则 XOR（$k_1,\cdots,k_N$）的值为 $1$，否则为 $0$）。以下是正式定义：

$$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$$

在上面的例子中，第一次的值 $a_1$ 计算如下：$\text{XOR}(1\cdot 1,0\cdot 0,1\cdot 1,1\cdot 1,0\cdot 0,1\cdot 0,1\cdot 1)=0$。

您将获得此类反馈移位寄存器的前 $2N$ 个输出值。从这些值中，您将尝试确定开关值 $s_i$。

输入格式

第一行包含一个整数 $N$，表示移位寄存器的大小。

第二行包含 $2N$ 个数字 0 或 1，表示移位的前 $2N$ 个输出位值。

输出格式

输出只包含一行。

• 如果至少有一个开关设置产生给定的寄存器输出值，输出一行 $N$ 个整数，其中第 $i$ 个整数代表第 $i$ 个开关值 $s_i$。任何此类开关设置的开关值都会被接受。
• 如果没有这样的开关设置，只输出 -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

提示

数据规模与约定

对于 $100\%$ 的数据，$1\le N\le 750$。

题目说明

来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2003 的 Shift Register。

由 @求学的企鹅 翻译整理。