7129: ABC269 —— E - Last Rook
[Creator : ]
Description
This is an interactive task (where your program interacts with the judge's program via input and output).
We have an $N$\-by-$N$ chessboard and $N$ rooks. Below, the square at the $i$\-th row from the top and $j$\-th column from the left is denoted by $(i, j)$.
Consider placing the rooks on squares of the chessboard. Here, you have to place the rooks so that all of the following conditions are satisfied.
- No row contains two or more rooks.
- No column contains two or more rooks.
Now, $N-1$ rooks are placed on the chessboard so that all of the above conditions are satisfied. You will choose a square that is not occupied by a rook and place a rook on that square. (It can be proved that there is at least one square on which a rook can be placed under the conditions.)
However, you cannot directly see which squares of the chessboard are occupied by a rook.
Instead, you may ask at most $20$ questions to the judge in the following manner.
- You choose integers $A$, $B$, $C$, and $D$ such that $1 \leq A \leq B \leq N, 1 \leq C \leq D \leq N$, and ask the number of rooks in the rectangular region formed by the squares $(i, j)$ such that $A \leq i \leq B, C \leq j \leq D$.
Find a square to place a rook.
We have an $N$\-by-$N$ chessboard and $N$ rooks. Below, the square at the $i$\-th row from the top and $j$\-th column from the left is denoted by $(i, j)$.
Consider placing the rooks on squares of the chessboard. Here, you have to place the rooks so that all of the following conditions are satisfied.
- No row contains two or more rooks.
- No column contains two or more rooks.
Now, $N-1$ rooks are placed on the chessboard so that all of the above conditions are satisfied. You will choose a square that is not occupied by a rook and place a rook on that square. (It can be proved that there is at least one square on which a rook can be placed under the conditions.)
However, you cannot directly see which squares of the chessboard are occupied by a rook.
Instead, you may ask at most $20$ questions to the judge in the following manner.
- You choose integers $A$, $B$, $C$, and $D$ such that $1 \leq A \leq B \leq N, 1 \leq C \leq D \leq N$, and ask the number of rooks in the rectangular region formed by the squares $(i, j)$ such that $A \leq i \leq B, C \leq j \leq D$.
Find a square to place a rook.
Input
This is an interactive task (where your program interacts with the judge's program via input and output).
First, receive the size of the chessboard, $N$, from Standard Input.
```
$N$
```
Next, repeat asking a question until you find a square to place a rook.
A question should be printed to Standard Output in the following format:
```
$?$ $A$ $B$ $C$ $D$
```
The response will be given from Standard Input in the following format:
```
$T$
```
Here, $T$ is the response to the question, or `-1` if the question is invalid or more than $20$ questions have been asked.
When the judge returns `-1`, the submission is already regarded as incorrect. In this case, terminate the program immediately.
When you find a square to place a rook, let $(X, Y)$ be that square and print an answer in the following format. Then, terminate the program immediately.
```
$!$ $X$ $Y$
```
If there are multiple appropriate answers, any of them will be accepted.
First, receive the size of the chessboard, $N$, from Standard Input.
```
$N$
```
Next, repeat asking a question until you find a square to place a rook.
A question should be printed to Standard Output in the following format:
```
$?$ $A$ $B$ $C$ $D$
```
The response will be given from Standard Input in the following format:
```
$T$
```
Here, $T$ is the response to the question, or `-1` if the question is invalid or more than $20$ questions have been asked.
When the judge returns `-1`, the submission is already regarded as incorrect. In this case, terminate the program immediately.
When you find a square to place a rook, let $(X, Y)$ be that square and print an answer in the following format. Then, terminate the program immediately.
```
$!$ $X$ $Y$
```
If there are multiple appropriate answers, any of them will be accepted.
Output
Sample Interaction
Below is an interaction where $N=3$ and the rooks are placed on $(1, 2)$ and $(2, 1)$.
Below is an interaction where $N=3$ and the rooks are placed on $(1, 2)$ and $(2, 1)$.