問題文

この問題はインタラクティブ問題です。

上下にカードが積まれた山が $3$ つあります。$3$ つの山にはそれぞれ番号 $1,2,3$ が振られています。

各山は、表面に $1$ つの整数が書かれた $2n$ 枚のカードからなります。山 $i\ (1\leq i\leq 3)$ の上から $k\ (1\leq k\leq 2n)$ 番目のカードに書かれた整数を $V _ {i, k}$ とします。

各カードは表面を下にして積まれているので、あなたは $V _ {i, k}$ の値を知りません。ただし、次の事実が成り立つことは分かっています。

• 各山のカードは上から下に向けて昇順に並んでいる。つまり、$1\leq i \leq 3,\ 1\leq k\lt l \leq 2n$ を満たす任意の整数 $i,k,l$ に対して、 $V _ {i, k} \leq V _ {i, l}$ が成り立つ。

さて、あなたは今から [ゲーム] をします。[ゲーム] は次の手順で進行します。

[ゲーム]

1. $X\leftarrow 0$ とする。
2. $3$ つの山のうち空でないものの個数を $a$ とする。
   • $a = 0$ ならば、ゲームを終了する。
   • $a = 1$ ならば、$X\leftarrow 10 ^ {100}$ と更新してゲームを終了する。
   • $a \geq 2$ ならば、あなたは $2$ つの空でない山 $i, j\ (i\neq j)$ を任意に選択する。選択した $2$ つの山から、それぞれ一番上に積まれているカードを取り除く。このとき取り除いた $2$ 枚のカードに書かれている整数を $x _ 1, x _ 2$ として、$X\leftarrow \max(X, x _1 + x _ 2)$ と更新して 2 に戻る。

あなたの目標はゲーム終了時の $X$ をできるだけ小さくすることです。ただし、ゲーム開始前にあなたは 高々 $3$ 回だけ 次のような [質問] をすることができます。

[質問]

• $1\leq i\leq 3, 1\leq x\leq 2n, 1\leq j\leq 3, 1\leq y\leq 2n$ を満たす整数 $i,x,j,y$ を選択し、$V _ {i, x} \lt V _ {j, y}$ が成り立つかどうかを質問する。

山札の情報を全て知っている場合 (つまり、全ての $V _ {i, k}$ が既知の場合) に達成しうる ゲーム終了時の $X$ の最小値を $X ^ \ast$ とします。

ゲーム終了時の $X$ がちょうど $X ^ \ast$ と一致するような操作の手順を $1$ つ求めてください。

なお、本問題のジャッジは適応的ではありません。つまり、各 $V_{i,k}$ の値は初めに固定されいて、途中で変化することはありません。

入出力

はじめに、正整数 $n$ が次の形式で $1$ 行に標準入力から与えられます。

$n$

あなたは 高々 $3$ 回だけ [質問] を行うことができます。[質問] において選択した整数 $i,x,j,y$ を次の形式で標準出力に出力してください。改行もしてください。ここで、$i, j$ は $1$ 以上 $3$ 以下の整数であり、かつ $x, y$ は $1$ 以上 $2n$ 以下の整数でなければなりません。

? $i\ x\ j\ y$

この [質問] に対して、$V _ {i, x} \lt V _ {j, y}$ が成り立つ場合は Yes が、成り立たない場合は No が $1$ 行に標準入力から与えられます。$V _ {i, x} = V _ {j, y}$ の場合も No が与えられることに注意してください。

高々 $3$ つの [質問] を終えたら、ゲーム終了時の $X$ がちょうど $X ^ \ast$ と一致するような操作の手順を次の形式で標準出力に出力してください。改行もしてください。ここで、$t = 1, 2, \ldots, 3n$ に対して $i _ t, j _ t$ は $t$ 回目の操作で選択する $2$ つの山の番号であり、相異なる $1$ 以上 $3$ 以下の整数でなければなりません。なお、ちょうど $3n$ 回の操作終了時に山札が全て空となり、かつ $X = X ^ \ast \lt 10 ^ {100}$ を満たすような操作手順が存在することを証明できます。

! $i_1\ j_1\ i_2\ j_2\ \cdots\ i_{3n}\ j_{3n}$

答えの出力を終えたら、直ちにプログラムを終了してください。

制約

• $n$ は $1$ 以上 $100$ 以下の整数
• カードに書かれた値は $1$ 以上 $10 ^ 6$ 以下の整数

注意

• 出力を行うたびに末尾に改行を入れて標準出力を flush してください。そうしなかった場合のジャッジ結果は不定です。
• 不正な出力を行った場合や規定の質問回数を超えた場合、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。特に、プログラムの実行中に実行時エラーが起こった場合のジャッジ結果は RE とは限りません。

サンプル

以下は $n=1$ で $V$ が次のように決まっている場合の入出力例です。ただし、実際には $V$ は入力として与えられない ことに注意して下さい。

• $V _ {1, 1} = 2, V _ {1, 2} = 3$
• $V _ {2, 1} = 3, V _ {2, 2} = 4$
• $V _ {3, 1} = 4, V _ {3, 2} = 5$

1

? 2 1 1 1

No

? 1 2 3 1

Yes

! 2 3 1 3 1 2