题目描述

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。

縦横 $N$ マスのチェス盤と $N$ 個のルークの駒があります。以下では上から $i$ 行目、左から $j$ 列目のマスを $(i,\ j)$ と表します。
チェス盤のマスにルークを置くことを考えます。ただし、あなたは次の条件をすべて満たすようにルークをチェス盤に置く必要があります。

• 1 つの行に $2$ 個以上のルークが存在しない。
• 1 つの列に $2$ 個以上のルークが存在しない。

今、チェス盤に $N-1$ 個のルークが上の条件をすべて満たした状態で置かれています。あなたはルークが置かれていないマスを 1 つ選び、そのマスにルークを置くことにしました。(上の条件をすべて満たすようにルークを置くことができるマスは少なくとも 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$ を満たすマス $(i,\ j)$ からなる長方形領域に置かれているルークの個数を聞く。

ルークを置くことができるマスを見つけてください。

Input & Output Format

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。

最初に、チェス盤のサイズ $N$ を標準入力から受け取ってください。

$N$

次に、ルークを置くことができるマスが見つかるまで質問を繰り返してください。
質問は、以下の形式で標準出力に出力してください。

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

これに対する応答は、次の形式で標準入力から与えられます。

$T$

ここで、$T$ は質問に対する答えです。ただし、不正な質問を行った、あるいは質問の回数が $20$ 回を超えた場合は $T$ は -1 となります。

ジャッジが -1 を返した場合、提出はすでに不正解とみなされています。この場合、ただちにプログラムを終了してください。

ルークを置くことができるマスを見つけたら、そのマスを $(X,\ Y)$ として、解答を以下の形式で出力してください。その後、ただちにプログラムを終了してください。

$!$ $X$ $Y$

答えが複数ある場合、どれを出力しても正解とみなされます。

题目大意

这是一道交互题。

现在有一个 $n \times n$ 的国际象棋棋盘，左上角为 $(1,1)$，右下角为 $(n,n)$，并且棋盘上已经放上了 $n - 1$ 个互相不能攻击的车。

互相不能攻击的定义：在任何一行中最多只有一辆车，在任何一列中最多只有一辆车。

容易证明，此时该棋盘还可以放一辆车，使得所有的 $n$ 辆车互相不能攻击。

现在你想在一个位置上摆上一辆车，使得所有的 $n$ 辆车互相不能攻击，设这个位置为 $(x,y)$。但是你不知道前 $n - 1$ 辆车的位置。

不过你可以进行不超过 $20$ 次的形如 ? a b c d 的询问，这时系统会返回左上角为 $(a,c)$，右下角为 $(b,d)$ 的子矩阵中的车的数量。询问的前提是 $1 \leq a \leq b \leq n$，$1 \leq c \leq d \leq n$。

你需要利用询问来求出 $(x,y)$。当你得到结果后，你应该输出形如 ! x y 的形式，其中 $x$ 和 $y$ 的定义如上述。

注意：

• 询问过后立即清空缓冲区。如果你不这么做，你可能会 TLE。

• 若你输出了无效询问（或回答），返回结果是不确定的。

• 若你在回答后不立即结束程序，返回的结果是不确定的。

$1 \leq n \leq 1000$。

提示

制約

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

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
• 対話の途中で不正な出力を行った場合のジャッジ結果は不定です。
• 解答を出力したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。

入出力例

以下は、$N=3$ で $(1,\ 2),\ (2,\ 1)$ にルークが置かれている場合の入出力例です。

入力 出力 説明 3 まず整数 $N$ が与えられます。 ? 1 2 1 3 $(A,B,C,D)=(1,2,1,3)$ として質問を行います。 2 質問の答えは $2$ なので、ジャッジはその値を返します。 ? 2 3 1 1 $(A,B,C,D)=(2,3,1,1)$ として質問を行います。 1 質問の答えは $1$ なので、ジャッジはその値を返します。 ? 1 3 3 3 $(A,B,C,D)=(1,3,3,3)$ として質問を行います。 0 質問の答えは $0$ なので、ジャッジはその値を返します。 ! 3 3 答えは $(3,\ 3)$ だとわかったので、それを出力します。