배틀십: 새로운 규칙

이 문제는 대화형 문제이다.

이반이 배틀십 게임의 새로운 규칙을 생각해 냈다.

• 게임은 $n \times n$ 크기의 보드에서 진행된다.
• 첫 번째 플레이어는 정수 $k$를 고른다 ($n \leq k \leq {\left\lceil \frac{n}{2} \right\rceil}^2$).
• 그다음 첫 번째 플레이어는 $k$개의 배를 보드에 놓는다. 배의 크기는 제한이 없으며, 차지하는 칸의 수가 $k$개 배의 모든 유효한 배치 중에서 최대가 되어야 한다.
• 각 배는 $1 \times a$ 또는 $a \times 1$ 크기의 직사각형이다 ($a$는 1 이상 $n$ 이하의 임의의 정수). 서로 다른 두 배의 칸은 변이나 모서리로 맞닿을 수 없다.

그다음 두 번째 플레이어가 게임을 시작한다.

• 두 번째 플레이어는 보드의 크기 $n$만 알고 있다.
• 두 번째 플레이어는 칸 $(x, y)$가 어떤 배에 의해 점유되어 있는지 질의할 수 있다.
• 두 번째 플레이어는 보드에서 비어 있는 $2 \times 2$ 정사각형을 하나 찾거나, 그런 정사각형이 없다고 답해야 한다.
• 두 번째 플레이어가 할 수 있는 질의는 최대 $6n$번이다. 두 번째 플레이어로서 게임에서 이겨 보자.

첫 번째 테스트의 보드는 아래 그림과 같다. 행은 $x$ 좌표, 열은 $y$ 좌표에 대응한다.

첫 번째 게임의 보드.	두 번째 게임의 보드.