보물 찾기

이 문제는 인터랙티브 문제이다.

근성은 $N \times N$크기의 격자 모양의 땅을 가지고 있다. 근성은 $i$번째 행 $j$번째 열에 있는 땅을 $(i, j)$ 칸이라 부르고, 그중 하나의 칸에 자신의 비밀이 숨겨진 보물을 묻어두었다.

그 후 보물의 위치를 까먹지 않기 위해서 보물이 있는 칸을 제외한 $N \times N-1$개의 칸에 보물의 위치에 대한 힌트가 적힌 쪽지를 묻어두었다. 쪽지에는 쪽지가 묻힌 땅과 보물이 묻힌 땅의 맨해튼 거리에 근성만 알고 있는 수 $X$를 XOR한 값을 적어두었다.

추가로 근성은 땅의 겉부분, 즉, $i = 1; i = N; j = 1; j = N$ 중 하나 이상을 만족하는 칸은 다른 사람이 비교적 찾기 쉽다고 생각하기 때문에 땅의 겉부분에는 보물을 묻어두지 않았다.

지금부터 근성이 숨긴 보물을 근성 몰래 찾아내려고 한다. 너무 오랫동안 보물을 찾으면 근성에게 들키게 될 가능성이 높다. 근성에게 들키지 않을 수 있도록 $N$번 이하로 땅을 파서 보물을 찾으시오.

• $3 \le N \le 1\\,000$
• $0 \le X < 2^{20}$