AT_abc269_e.[ABC269E] Last Rook

本题为交互题（你的程序需要与评测程序通过输入输出进行交互）。

有一个 $N \times N$ 的国际象棋棋盘和 $N$ 个车（Rook）棋子。下面将棋盘从上到下第 $i$ 行，从左到右第 $j$ 列的格子记作 $(i,\,j)$。

现在要在棋盘上放置车棋子，但你需要满足以下所有条件：

• 每一行不能有两个或以上的车。
• 每一列不能有两个或以上的车。

现在，棋盘上已经有 $N-1$ 个车，且上述条件都已满足。你需要选择一个没有放车的格子，并在该格子上放置一个车（可以证明至少存在一个满足条件的格子）。

但是，你无法直接知道棋盘上哪些格子已经有车。
不过，你可以向评测系统最多询问 $20$ 次以下问题：

• 选择整数 $A,B,C,D$，满足 $1 \leq A \leq B \leq N,\,1 \leq C \leq D \leq N$。你可以询问在 $A \leq i \leq B,\,C \leq j \leq D$ 组成的矩形区域内有多少个车。

请找出可以放置车的格子。

本题为交互题（你的程序需要与评测程序通过输入输出进行交互）。

首先，你需要从标准输入读取棋盘的大小 $N$。

$N$

接下来，在找到可以放置车的格子之前，你可以多次进行询问。
每次询问，请按如下格式输出到标准输出：

? $A$ $B$ $C$ $D$

评测系统会返回如下格式的响应：

$T$

其中，$T$ 是你询问的区域内的车的数量。如果你进行了非法询问，或者询问次数超过 $20$ 次，则 $T$ 会为 $-1$。

如果评测系统返回 $-1$，则你的提交已被判为不正确，此时请立即终止程序。

当你找到可以放置车的格子后，请将该格子的坐标 $(X,\,Y)$ 按如下格式输出，并立即终止程序：

! $X$ $Y$

如果有多个答案，输出任意一个都视为正确。

无

限制

• $2 \leq N \leq 10^3$
• $N$ 为整数

注意事项

• 每次输出后，请在末尾加上换行并刷新标准输出。否则可能会被判为 TLE。
• 交互过程中如果输出不合法，评测结果不确定。
• 输出答案后请立即终止程序，否则评测结果不确定。

输入输出样例

以下是 $N=3$，且 $(1,\,2),\,(2,\,1)$ 已经有车的输入输出示例。

输入 输出 说明
3 首先给出整数 $N$。
? 1 2 1 3 询问 $(A,B,C,D)=(1,2,1,3)$ 区域。
2 回答为 $2$，表示该区域有 $2$ 个车。
? 2 3 1 1 询问 $(A,B,C,D)=(2,3,1,1)$ 区域。
1 回答为 $1$，表示该区域有 $1$ 个车。
? 1 3 3 3 询问 $(A,B,C,D)=(1,3,3,3)$ 区域。
0 回答为 $0$，表示该区域没有车。
! 3 3 确定答案为 $(3,\,3)$，输出即可。

由 ChatGPT 4.1 翻译