공원

Vasi는 마침내 Ruse를 방문해 공원에서 산책하기로 했다. 여행 가이드에 따르면 공원은 직사각형 모양이고 긴 변의 길이는 $N$이다. 이 두 변 각각에는 $N + 1$개의 흥미로운 장소(카페, 테니스 코트, 분수 등)가 있어서 모두 $2N + 2$개의 흥미로운 장소가 있다. 이 장소들은 번호가 매겨져 있고 아래 그림처럼 골목으로 연결되어 있다(이 경우 $N = 3$). 공원에는 입구가 하나(번호 $1$인 장소)와 출구가 하나(번호 $2N + 2$인 장소) 있다.

공원의 모든 골목은 일방통행이고 산책할 때는 각 골목의 방향을 따라야 한다. 골목의 방향은 순환이 존재하지 않도록 정해져 있다. 또한 입구는 모든 골목이 나가는 쪽인 유일한 장소이고 출구는 모든 골목이 들어오는 쪽인 유일한 장소이다. 다른 모든 장소에는 다음 규칙이 성립한다. 들어오는 골목과 나가는 골목이 모두 있다.

어떤 골목이 더 작은 번호의 장소에서 더 큰 번호의 장소로 향하면 양의 방향이라고 하고, 그렇지 않으면 음의 방향이라고 하자. Vasi는 입구에서 나가는 두 골목과 출구로 들어오는 두 골목이 양의 방향이라는 것을 알고 있지만(입구가 번호 $1$이고 출구가 번호 $2N + 2$이므로), 다른 골목의 방향에 대해서는 아무것도 모르며 산책을 계획하려면 그 방향을 알아내야 한다.

공원 입구에는 수학과 정보 문제를 좋아하는 사람들을 위해 특별한 프로그램이 설치된 컴퓨터가 있다. 이 프로그램은 다음과 같은 이상한 질문에 답한다. 연결하는 장소의 번호로 표현되는 임의의 골목 목록을 프로그램에 주면 프로그램은 그 방향들의 XOR 연산 결과를 반환한다(양의 방향은 1, 음의 방향은 0으로 표현한다). 두 한 자리 이진수의 XOR은 두 수가 다르면 1, 같으면 0이다. 피연산자가 둘보다 많으면 처음 두 개를 XOR한 뒤 그 결과와 세 번째 피연산자를 XOR하고, 이런 식으로 계속한다. 프로그램은 주어진 목록에 골목이 하나만 있으면 그 골목의 방향을 그대로 반환한다.

Vasi는 프로그램에 너무 많은 질문을 하지 않고 모든 골목의 방향을 알아내려고 한다.

심사위원단은 공원 입구의 프로그램을 복사해 채점 시스템에 올려 두었다. 위에서 설명한 방식의 질문을 하고 알아낸 방향을 제출하며 프로그램과 통신하는 함수 run을 작성해 Vasi를 도와주자. 함수의 실행이 끝난 뒤에는 공원에 있는 모든 골목의 방향을 올바르게 알아내어 제출한 상태여야 한다.

• $1 ≤ N ≤ 100 000$