33715번 - 보물 찾기 인터랙티브

문제

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

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

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

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

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

인터랙션

첫 번째 줄에 땅의 크기 $N$이 주어진다.

당신은 하나의 줄에 다음의 형식과 개행 문자를 출력한 뒤 표준 출력 버퍼를 비워서 땅을 팔 수 있다.

i j

이는 $(i, j)$ 칸을 파본다는 의미이다. 여기서 1ドル \le i \le N; 1 \le j \le N$이여야 한다. 이후 땅을 판 것에 대한 결과로 정수 $K$가 주어진다.

만약 $K$가 $-1$이라면 보물을 찾았다는 것을 의미하고 즉시 프로그램을 종료해야 한다. 이 경우 맞았습니다!!를 받게 된다. 보물을 찾지 못했다면 해당 칸에 묻혀있던 힌트가 적힌 쪽지의 내용이 주어진다. 이때 0ドル \le K < 2^{20}$ 이다.

잘못된 형식으로 출력하거나, $N$번을 초과하여 땅을 파는 경우 예상치 못한 채점 결과를 받을 수 있다.

입력

출력

제한

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

노트