题目描述

计算机的寄存器存储 $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×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$ 计算如下：$\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$ 个输出位值。

输出格式

输出只包含一行。如果有一个开关设置产生给定的寄存器输出值，输出任何此类开关设置的开关值 $s_i$，从 $s_1$ 开始。如果没有这样的开关设置，只输出数字 $-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 \leq N \leq 750$。

题目说明

来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2002 的 Shift Register。
由 @求学的企鹅 翻译整理。