問題文

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

$N$ 頂点からなる有向グラフが与えられます。頂点には $1$ から $N$ の番号が振られています。

このグラフには $\frac{N(N-1)}{2}$ 本の長さ $1$ の辺があり、以下の性質を満たしています。

• $1\leq i\lt j \leq N$ を満たすすべての整数の組 $(i, j)$ について、辺 $i \rightarrow j$ または辺 $j \rightarrow i$ のどちらか $1$ つが存在する。

あなたは以下の質問を $4000$ 回まで行うことができます。

• $1\leq a, b\leq N, a \neq b$ を満たす整数の組 $(a, b)$ を選ぶ。$a\to b$ の辺が存在するか聞く。

このグラフの最長パス（同じ頂点を $2$ 度通らない）を $1$ つ見つけてください。

入出力

まず、頂点数 $N$ が標準入力に与えられます。

$N$

次に、最長パスが見つかるまで質問を繰り返してください。質問は以下の形式で標準出力に出力してください。

$?$ $a$ $b$

ただし $1\leq a, b\leq N, a\neq b$ を満たしている必要があります。また、最後に改行してください。

この質問に対する応答は標準入力に以下の形式で与えられます。

$T$

ここで $T=0$ または $T=1$ であり、$T=1$ なら $a\to b$ の辺が存在することを、$T=0$ なら存在しないことを表します。

ただし質問の回数が $4000$ を超えたり、質問の制約が守られていない場合、ジャッジは $T=-1$ を返しただちに終了します。

最長パスを発見した場合、以下の形式で報告してください。

$!$
$L$
$C_0$ $C_1$ $\ldots$ $C_L$

ここで $L$ は最長パスの長さであり、$C_i (0\leq i \leq L)$ は（この順に）パスが通る頂点を表します。（パスの長さが $L$ なので、通る頂点は $L+1$ 個であることに注意してください。）

ここで以下の制約が満たされている必要があります。

• $1\leq i\leq L$ を満たす整数 $i$ について、$C_{i-1}\to C_i$ の辺が存在する。
• $0\leq i\lt j\leq L$ を満たす整数の組 $(i, j)$ について、$C_i \neq C_j$

考えられる答えが複数存在する場合、どれを出力しても正解と判定されます。

注意

各出力後は改行し、必ず flush を行ってください。また質問の結果を必ず受け取ってください。

答えを出力したあとは、すぐにプログラムを終了してください。

制約

• 入力はすべて整数
• $2\leq N\leq 500$
• グラフは問題文中の性質をみたす
• グラフは対話の開始前に決定される

サンプル

3
1
1
1

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