最后的车

题目描述

这是一个交互式任务(你的程序通过输入输出与评测程序交互)。

我们有一个 $N \times N$ 的棋盘和 $N$ 个车。下面,从上数第 $i$ 行、从左数第 $j$ 列的格子记为 $(i, j)$。

考虑把车放在棋盘的格子上。放置时,必须满足以下所有条件:

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

现在,已有 $N-1$ 个车以满足上述所有条件的方式放置在棋盘上。你需要选择一个没有被车占据的格子,并在该格子上放置一个车。(可以证明,在满足条件的情况下,至少存在一个可以放置车的格子。)

但是,你无法直接看到棋盘上哪些格子被车占据。

作为代替,你可以按以下方式向评测程序提问最多 $20$ 次:

你选择满足 $1 \leq A \leq B \leq N, 1 \leq C \leq D \leq N$ 的整数 $A$, $B$, $C$, $D$,询问由满足 $A \leq i \leq B, C \leq j \leq D$ 的格子 $(i, j)$ 构成的矩形区域内车的个数。

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

输入格式

这是一个交互式任务(你的程序通过输入输出与评测程序交互)。

首先,从标准输入读取棋盘大小 $N$:

$N$

接下来,每次提问后,评测程序将从标准输入给出回答:

$T$

这里,$T$ 是提问的回答;如果提问无效或提问次数超过 $20$ 次,则 $T$ 为 $-1$。

输出格式

重复提问,直到找到可以放置车的格子。

提问按以下格式输出到标准输出:

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

当评测程序返回 $-1$ 时,该提交已被视为不正确。此时请立即终止程序。

当你找到可以放置车的格子时,设该格子为 $(X, Y)$,按以下格式输出答案,然后立即终止程序:

$!$ $X$ $Y$

样例

本题为交互式任务,没有样例。

数据范围

• $2 \leq N \leq 10^3$
• $N$ 是整数。

提示

每次输出后都要换行并刷新标准输出(flush)。否则可能会超时(TLE)。

如果有多个合适的答案,输出任意一个即可。答案不唯一,输出任意合法解即可。