問題文

物理好き君は誕生日にたくさんのプレゼントをもらいましたが、２次元平面上のどこかになくしてしまいました。

あなたは、範囲を指定するとその範囲にプレゼントが存在するかを判定してくれる機械を持っています。

しかし機械を動かすのにはコストがかかるため、限られた回数内で、物理好き君のプレゼントをすべて見つけてあげてください。

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

また、ジャッジは適応的ではありません。各テストケースにおいて、プログラムの実行前にプレゼントの個数や位置は決まっており、変わることはありません。

２次元平面上に $N$ 個の点があり、 $i$ 個目の点の座標は $(X_i, Y_i)$ です。ただし、 $N, X_i, Y_i$ は与えられず、ジャッジシステムはこれらの値を隠し持っています。

あなたは、ジャッジシステムに対して以下の質問を $8000$ 回まで行うことができます。

• $0$ 以上 $10^6$ 以下の整数 $x_l, x_r, y_l, y_r$ を選ぶ。ただし、 $0 \leq x_l \leq x_r \leq 10^6, 0 \leq y_l \leq y_r \leq 10^6$ を満たさなければならない。そして、 $1$ 以上 $N$ 以下の整数 $i$ であって、 $x_l \leq X_i \leq x_r$ かつ $y_l \leq Y_i \leq y_r$ を満たすものが存在するかどうかを聞く。

$8000$ 回以下の質問で $N$ および集合 $\{ (X_i, Y_i) \}$ を特定してください。

制約

• $1 \leq N \leq 100$
• $0 \leq X_i, Y_i \leq 10^6$
• $i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)$
• $N, X_i, Y_i$ はすべて整数

入出力

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

最初は入力から何も与えられません。

以下の質問を $0$ 回以上 $8000$ 回以下繰り返してください。

質問は、選ぶ２次元平面上の範囲を $[x_l, x_r + 1)\times[y_l, y_r + 1)$ としたとき、整数 $x_l, x_r, y_l, y_r$ $(0 \leq x_l \leq x_r \leq 10^6, 0 \leq y_l \leq y_r \leq 10^6)$ を用いて以下の形式で標準出力に出力してください

? $x_l\ x_r\ y_l\ y_r$

その後、$1$ 以上 $N$ 以下の整数 $i$ であって、 $x_l \leq X_i \leq x_r$ かつ $y_l \leq Y_i \leq y_r$ を満たすものが存在する場合は

1

存在しない場合は

0

が以上の形式で標準入力から与えられます。

ただし、質問が不当であった場合、-1が標準入力から与えられます。

-1

具体的には

• 出力した $x_l, x_r, y_l, y_r$ が制約を満たさなかった
• $8000$ 回を超えて質問をした

の少なくとも１つを満たした場合、出力されます。

このとき、不正解であることが確定しているため、ただちにプログラムを終了してください。

最後に、次の形式で $N+1$　行標準出力することで、プレゼントの個数 $N$ と位置の集合 ${ (X_i, Y_i) }$ を解答します。

! $N$
$X_1\ Y_1$
$X_2\ Y_2$
  $\vdots$
$X_N\ Y_N$

正確には、まず1行目に!とプレゼントの個数 $N$ を空白区切りで標準出力し改行してください。

! $N$

次の $i + 1$ 行目 $(1 \leq i \leq N)$ には $i$ 番目のプレゼントの位置 $X_i, Y_i$ を空白区切りで標準出力し改行してください。

$X_i\ Y_i$

ただし、 すべての整数の組 $1 \leq i < j \leq N$ について、$(X_i, Y_i) \neq (X_j, Y_j)$ を満たす必要があります。

また、集合として ${ (X_i, Y_i) }$ が答えと一致していたら正解とみなされるため、プレゼントの位置の順番はジャッジ結果に影響しません。

この出力の後、ただちにプログラムを終了してください。

なお、全ての出力について、出力が指定された形式を満たさなかった場合もプログラムが不正解とみなされます。その後-1が返答されるので、その場合も直ちにプログラムを終了してください。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE や WA となる可能性があります。
• 解答を出力したら（または-1を受け取ったら）直ちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
• 余計な改行は不正な形式の出力とみなされることがあることに注意してください。
• この問題のジャッジシステムは、適応的ではありません。つまり、各テストケースにおいて、プログラムの実行前にプレゼントの個数や位置は決まっており、変わることはありません。

入出力例

この入力では $N=3, { (X_i, Y_i) } = { (1, 1), (2, 2), (5, 5) }$ とします。