Hidden Rook

시간 제한15초메모리 제한256 MB

요약

n 곱하기 m 체스판에 숨은 룩의 위치를, 부분 직사각형에서 룩이 공격하는 칸 수를 묻는 질의를 최대 네 번 써서 찾는다.

난이도: 보통10점 중 4점
유형: 완전 탐색, 수학, 구간, 구현
정답자: 아직 제출이 없습니다

문제

This problem is interactive.

Roman hid a rook on an $n \times m$ chessboard. You need to find its exact position. You can ask Roman the following question at most 4 times: "How many cells $(i, j)$ , where $X\_1 \le i \le X\_2$ and $Y\_1 \le j \le Y\_2$ , are under the hidden rook's attack?" A rook attacks all cells in the same row or column, including its own cell.

입력

The first line contains an integer $t$ , the number of test cases ( $1 \le t \le 15\\,000$ ).

예제1

예제 1

입력

예상 출력