시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 1 1 25.000%

문제

레지스터는 계산을 하기 위해서 N비트를 저장한다. 시프트 레지스터는 레지스터의 특수한 형태로, 모든 비트를 한 자리씩 시프트 시킬 수 있다.

시프트 레지스터의 결과를 이용해 다음과 같이 바이너리 유사난수를 얻을 수 있다. 크기가 N인 시프트 레지스터에 a1, a2, ..., aN이 저장되어 있다. 클럭틱마다 레지스터는 가장 오른쪽 비트 aN을 출력한다. 다른 비트는 모두 오른쪽으로 한 칸 이동하게 된다. 첫 번째 비트 a′1은 다음과 같은 방법으로 구할 수 있다.

레지스터의 모든 비트는 아래 그림과 같이 스위치를 통해 XOR 게이트와 연결되어 있다. 각각의 비트 i마다 스위치 si(1 또는 0)가 존재하며, 스위치는 ai를 XOR 게이트로 보낼지 말지를 결정하게 된다. ki = si·ai라고 했을 때, a′1은 XOR게이트의 출력값 XOR(k1, ..., kN)이 된다. (k1, ..., kN에서 1의 개수가 홀수개이면 XOR(k1, ..., kN) = 1이고, 아니면 0이다)

  • a′1 = XOR(k1, ..., kN)
  • a′i = ai-1 for 2 ≤ i ≤ N
  • output = aN

위의 예제에서 틱 1에서 a1은 다음과 같이 XOR(1·1, 0·0, 1·1, 1·1, 0·0, 1·0, 1·1) = 0

시프트 레지스터의 결과 중 처음 2N개가 주어진다. 이 때, 스위치 값 si를 결정하는 프로그램을 작성하시오.

입력

첫째 줄에 시프트 레지스터의 크기 N이 주어진다. (1 ≤ N ≤ 750) 둘째 줄에는 시프트 레지스터의 결과중 처음 2N개가 주어지며, 0 또는 1이다.

출력

입력으로 주어진 레지스터 출력 결과를 갖는 스위치 세팅이 존재하는 경우에는 si를 공백으로 구분해서 출력하고, 존재하지 않는 경우에는 -1을 출력한다.

가능한 스위치 세팅이 여러가지인 경우에는 아무거나 출력한다.

예제 입력

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

예제 출력

1 0 1 1 0 1 1

힌트