問題文

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

遥か彼方の銀河には、$N$ 個の宇宙ステーションがあり、$1$ から $N$ までの番号が振られています。このうちのいくつかのステーション間は、双方向に移動可能な「透明なワームホール」で結ばれています。 星図データが完全に失われたため、私たちは宇宙ステーションの数 $N$ しか知らず、ワームホールの総数 $M$ や、ワームホールがどのステーション同士を繋げているかといった接続情報は一切わかりません。ただし、ワームホールの総数 $M$ は $400$ を超えないことが分かっています。

あなたは星図を復元するために、システムの「重力波探知機」にクエリを送信してテストすることができます。 1回のクエリでは、互いに素な（共通部分を持たない）2つの宇宙ステーションの集合 $A$ と $B$ を指定して送信します。ジャッジシステムは直ちに探知機を起動し、集合 $A$ のいずれかのステーションと集合 $B$ のいずれかのステーションを直接結ぶワームホールが $1$ つ以上存在するかどうかを返します。

できるだけ少ないクエリ回数で、ワームホールがどのステーション同士を繋げているかを全て特定してください。

入出力

最初に、宇宙ステーションの数 $N$ が標準入力から与えられます。

$N$

続いて、あなたのプログラムは重力波探知機にクエリを送信することができます。クエリは以下の形式で標準出力に出力してください。

? $K_A\ K_B\ A_1\ A_2\ \cdots \ A_{K_A}\ B_1\ B_2\ B_{K_B}$

ここで、$K_A, K_B$ はそれぞれ指定する集合 $A, B$ の要素数であり、$K_A \ge 1$ かつ $K_B \ge 1$ を満たす整数でなければなりません。 また、$A$ は $K_A$ 個のステーションからなる集合 $\{A_1, A_2, \dots, A_{K_A}\}$ を、$B$ は $K_B$ 個のステーションからなる集合 $\{B_1, B_2, \dots, B_{K_B}\}$ を表します。 指定する各ステーションの番号は $1 \le A_i, B_j \le N$ を満たす互いに異なる整数であり、２つの集合に共通のステーションが含まれていてはなりません（$A \cap B = \emptyset$）。

クエリを送信した後、ジャッジシステムから結果 $R$ が標準入力に与えられます。

$R$

• $R = 1$ のとき：集合 $A$ と集合 $B$ の間に少なくとも1つのワームホールが存在します。
• $R = 0$ のとき：集合 $A$ と集合 $B$ の間には1つもワームホールが存在しません。
• $R = -1$ のとき：送信したクエリの形式が間違っていた場合や、クエリ制限回数を超過した場合に与えられます。この場合、プログラムを直ちに終了させてください。そうしない場合のジャッジ結果は不定です。

すべての接続関係が特定できた場合、以下の形式で解答を出力し、プログラムを正常終了させてください。解答の出力はクエリ回数にカウントされません。

! $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

ここで、$M$ は存在するワームホールの総数です。また、$m\ (1 \le m \le M)$ 個目のワームホールが繋いでいるステーションの番号を $u_m, v_m$ とします。 ワームホールを出力する順番や、各ワームホールの端点 $u_m, v_m$ の順番は問いません。

【注意】 各出力（クエリおよび解答）の後には必ず標準出力をフラッシュ (flush) してください。フラッシュしない場合、TLE や WA となる可能性があります。 最後に改行してください。

制約

• $2 \le N \le 400$
• $N$ は整数である
• 隠されたワームホールの総数 $M$ は $0 \le M \le 400$ を満たす
• あるステーションから自分自身へ繋がるワームホールや、同じステーションのペアを結ぶ複数のワームホールは存在しない
• クエリ送信回数の上限は $4,500$ 回

サンプル

4
1
0
1
1

? 1 3 1 2 3 4
? 1 1 1 3
? 1 1 1 2
? 2 2 1 2 3 4
! 2
1 2
2 4

3
0

? 1 2 1 2 3
! 0

3
1
1
1
1

? 1 2 1 2 3
? 1 1 1 2
? 1 1 1 3
? 1 1 2 3
! 3
1 2
1 3
2 3