시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
15 초 | 256 MB | 35 | 10 | 9 | 28.125% |
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$).
The interaction in each test case starts with two integers, $n$ and $m$: the chessboard dimensions ($3 \le n, m \le 15$).
To ask Roman a question, print "?
$X_1$
$Y_1$
$X_2$
$Y_2$" ($1 \le X_1 \le X_2 \le n$, $1 \le Y_1 \le Y_2 \le m$). After that, you will receive an integer $K$: the number of cells $(i, j)$, where $X_1 \le i \le X_2$ and $Y_1 \le j \le Y_2$, that are under the hidden rook's attack. You can ask at most 4 questions in each test case.
To report the answer, print "!
$X$
$Y$", where $(X, Y)$ is the hidden rook's cell.
After making each query, do not forget to print the newline character and flush the output. You can use the following commands:
for other languages, see their documentation. You will get the "Idleness limit exceeded
" verdict if you fail to do so.
2 6 6 8 2 7 5 11 4
? 1 1 3 6 ? 2 2 2 3 ! 2 3 ? 1 1 7 5 ? 1 1 1 4 ! 1 4