재귀적으로 도는 개미

$2^n \times 2^n$ 크기의 체스판이 있고, 일부 칸은 금지 칸으로 표시되어 있다. 개미는 금지 칸을 제외한 모든 칸을 정확히 한 번씩 방문해야 한다. 이동은 왼쪽 위 칸 $(0, 0)$ 에서 시작하며, 이 시작 칸은 절대 금지 칸이 아니다. 마지막에는 판 밖으로 나가야 하므로, 개미는 판의 네 변(바깥 테두리) 중 한 곳에 있는 칸에서 경로를 끝내야 한다. 한 번의 이동으로 개미는 상하좌우로 인접한 칸(최대 네 칸) 중 하나로 갈 수 있다.

이 경로는 재귀적이다. $2^k \times 2^k$ 크기의 블록을 도는 방법은 다음과 같다. 블록을 $2^{k-1} \times 2^{k-1}$ 크기의 사분면 네 개로 나눈 뒤, 각 사분면을 차례대로 돈다. 개미가 어떤 사분면에 들어가면, 그 사분면 안의 금지되지 않은 칸을 모두 방문하기 전에는 그 사분면을 떠날 수 없다.

그림은 $2^3 \times 2^3$ 판 위의 재귀적 경로 두 개를 보여 준다. 둘 다 $(0, 0)$ 칸에서 시작하며, 첫 번째는 위쪽 변에서, 두 번째는 왼쪽 변에서 끝난다.

다음을 수행하는 프로그램을 작성하시오.

• 판의 크기를 정하는 $n$ 과 금지 칸의 개수 $m$, 그리고 모든 금지 칸의 좌표를 입력받는다.
• 네 변 각각에 대해, 위에서 설명한 재귀적 경로가 끝날 수 있는 칸을 하나 찾거나, 그런 칸이 존재하지 않음을 판정한다.
• 결과를 출력한다.

네 모서리 칸은 각각 동시에 두 변에 속한다.

첫째 줄에 양의 정수 $n$ 이 주어지며 $n \le 30$ 이다. 판의 크기는 $2^n \times 2^n$ 이다. 둘째 줄에 금지 칸의 개수 $m$ 이 주어지며 $m \le 50$ 이다.

이어지는 $m$ 개의 줄에는 각각 공백 하나로 구분된 음이 아닌 두 정수 $i$ 와 $j$ 가 주어진다. $i$ 는 금지 칸의 행 번호, $j$ 는 열 번호이다. 행과 열은 $0$ 부터 $2^n - 1$ 까지 번호가 매겨지고, 왼쪽 위 칸이 $(0, 0)$ 이다. 시작 칸 $(0, 0)$ 은 절대 금지 칸이 아니다.

네 줄을 출력한다. 각 줄에는 공백 하나로 구분된 음이 아닌 두 정수(해당 경로가 끝나는 칸의 행 번호와 열 번호)를 출력하거나, 그런 칸이 없으면 NIE 를 출력한다.

첫째 줄은 위쪽 변에서 끝나는 경로, 둘째 줄은 오른쪽 변, 셋째 줄은 아래쪽 변, 넷째 줄은 왼쪽 변에 대한 것이다.