34229번 - 극대 찾기 인터랙티브

문제

크기 $N \times N$의 숨겨진 배열 $A$가 있다. 배열 $A$의 원소는 1ドル$부터 $N^2$사이의 서로 다른 정수로 이루어져 있다.

다음 조건을 만족하는 $(x,y)$를 극대라 한다.

• $x>1$인 경우, $A_{x,y} > A_{x-1,y}$를 만족한다.
• $x<N$인 경우, $A_{x,y} > A_{x+1,y}$를 만족한다.
• $y>1$인 경우, $A_{x,y} > A_{x,y-1}$를 만족한다.
• $y<N$인 경우, $A_{x,y} > A_{x,y+1}$를 만족한다.

당신은 배열 $A$에서 극대를 찾아야 한다.

답을 찾기 위해, 당신은 채점 시스템에 두 종류의 연산을 최대 27ドル$회 할 수 있다:

• V $i$ $j$ $k$: $\max(A_{i,j}, A_{i+1,j}, \ldots, A_{i+k-1,j})$의 값을 묻는다.
• H $i$ $j$ $k$: $\max(A_{i,j}, A_{i,j+1}, \ldots, A_{i,j+k-1})$의 값을 묻는다.

극대 $(x,y)$를 찾아보자. 만약 그러한 답이 여러 가지 있다면, 아무 답이나 찾아보자.

입력

첫째 줄에 $N$이 주어진다. (2ドル \leq N \leq 2,000円$)

이후 당신과 채점 시스템과의 인터랙션이 진행된다.

출력

제한

인터랙션

당신은 표준 출력에 다음 연산을 각 줄에 출력하는 것으로, 채점 시스템과 인터랙션할 수 있다. 각 토큰은 공백으로 구분하며, 각 연산의 끝에 개행문자를 출력하여야 한다.

당신은 채점 시스템에게 V연산과 H연산을 총합하여 최대 27ドル$회 할 수 있다.

• V $i$ $j$ $k$:
  • $\max(A_{i,j}, A_{i+1,j}, \ldots, A_{i+k-1,j})$의 값이 다음 줄에 입력된다.
  • 1ドル \leq i \leq N-k+1; 1 \le j \le N$
• H $i$ $j$ $k$:
  • $\max(A_{i,j}, A_{i,j+1}, \ldots, A_{i,j+k-1})$의 값이 다음 줄에 입력된다.
  • 1ドル \leq i \leq N; 1 \leq j \leq N-k+1$

만약 극대 점 $(x,y)$을 알아냈다면 다음 연산을 통해 답을 제출할 수 있다.

• ! $x$ $y$
  • 해당 연산 이후에는 프로그램을 종료하여야 한다.
  • 이 연산은 연산 제한에 포함되지 않는다.

만약 연산이 잘못된 출력이거나 제한을 초과하였다면 당신은 -1을 다음 줄에 입력받으며 이 입력이 주어질 경우 프로그램을 즉시 종료해야 한다.

채점 시스템은 적응적이지 않다. 즉 처음에 배열 $A$는 정해져 있으며 상호작용 도중에 $A$를 바꾸지 않는다.

각 연산 이후에는 표준 출력 버퍼를 비워야 한다.

각 언어별로 표준 출력 버퍼를 비우는 방법은 다음과 같다. 기타 언어의 경우, 언어의 레퍼런스 페이지를 참조하여라.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java, Kotlin: System.out.flush()
• Python: sys.stdout.flush()

힌트