시프트 레지스터

레지스터는 계산에 사용할 $N$개의 비트를 저장한다. 시프트 레지스터는 레지스터의 특수한 형태로, 저장된 모든 비트를 한 칸씩 옮길 수 있다.

시프트 레지스터를 이용하면 다음과 같이 이진 유사난수열을 만들 수 있다. 크기가 $N$인 시프트 레지스터에 비트 $a_1, a_2, \ldots, a_N$이 저장되어 있다. 매 클럭마다 레지스터는 가장 오른쪽 비트 $a_N$을 출력하고, 나머지 비트는 모두 오른쪽으로 한 칸씩 이동한다. 비어 있는 첫 번째 자리 $a'_1$은 아래 방법으로 채운다.

레지스터의 각 비트는 아래 그림처럼 스위치를 통해 하나의 XOR 게이트에 연결되어 있다. 비트 $i$마다 스위치 $s_i \in \{0, 1\}$가 있어, 그 비트 $a_i$를 XOR 게이트로 보낼지($s_i = 1$) 보내지 않을지($s_i = 0$)를 정한다. $k_i = s_i \cdot a_i$라 하면 $a'_1$은 XOR 게이트의 출력 $\mathrm{XOR}(k_1, \ldots, k_N)$과 같다. 즉 $k_1, \ldots, k_N$ 중 1의 개수가 홀수이면 1, 짝수이면 0이다.

• $a'_1 = \mathrm{XOR}(k_1, \ldots, k_N)$
• $a'_i = a_{i-1}$ (단, $2 \le i \le N$)
• 출력 $= a_N$

예를 들어 위 그림의 상태에서 첫 클럭에 새로 채워지는 비트는 $\mathrm{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_1, \ldots, s_N$을 구하는 프로그램을 작성하시오.

첫째 줄에 시프트 레지스터의 크기 $N$이 주어진다. ($1 \le N \le 750$)

둘째 줄에 시프트 레지스터가 출력한 수열의 처음 $2N$개가 공백으로 구분되어 주어지며, 각 값은 0 또는 1이다.

주어진 출력 수열을 만들어 내는 스위치 설정이 존재하면, 그러한 설정 중 사전순으로 가장 앞서는 것을 출력한다. 즉 $s_1, s_2, \ldots, s_N$을 공백으로 구분해 한 줄에 출력하되, 여러 설정이 가능하면 $s_1$부터 차례대로 비교했을 때 처음으로 값이 달라지는 자리에서 0을 1보다 앞세운(더 작은) 설정을 출력한다. 어떤 설정으로도 주어진 출력을 만들 수 없으면 -1을 출력한다.