問題文

この問題はリアクティブ形式の（ジャッジ側のプログラムと対話的に実行する必要がある）問題です。

最初に $2$ 以上の整数 $N$ が与えられます。

ある村には $N$ 個の広場と、それらを双方向に結ぶ $0$ 本以上の道があります。道の情報は入力で与えられません。

広場は $N$ 以下の各正整数 $i$ で番号付けられ広場 $i$ と呼ばれます。

道は相異なる $2$ つの広場を結んでおり、その長さは正整数です。相異なる $2$ つの広場それぞれについて、それらを結ぶ道は高々 $1$ 本しかありません。

広場間を移動する経路の経路長とは、通った道の長さの総和です。ただしここでは経路と言った時、$1$ 本以上の道のみを重複なく通って移動するものを指します。

$N$ 以下の正整数全体の集合を $I_N$ と置き、長さ $1$ 以上の $I_N$ の順列全体の集合を $P_N$ と置きます。

$p \in P_N$ に対し、$p$ に沿う順路とは、広場間を移動する経路であって、通る順に広場の番号を並べて得られる数列が $p$ の連続とは限らない部分列であって $p$ の先頭と末尾を含むものとなるもののことです。

$p \in P_N$ に対し、$p$ に沿う順路が存在するならばその経路長の最小値を $L(p)$ と置き、存在しないならば $L(p) = \infty$ と定めます。ただし $\infty$ は全ての正整数より大きい値として扱います。

長さ $N$ 未満の $p \in P_N$ に対し、$p$ の成分に現れない $j \in I_N$ 全体における組 $(L(p \textrm{⌒} (j)),j)$ の辞書順での最小値を $(w_p,j_p)$ と置きます。

ただし $p \textrm{⌒} (j)$ は $p$ の末尾に $j$ を挿入することで得られる $I_N$ の順列を表します。また実際に最小値が存在することは証明可能です。

順路大好きbotは順路が大好きなbotです。

以下の一連のやり取り（以下、質問と呼ぶ）を $0$ 回以上 $N$ 回以下の好きな回数行います。

1. まずあなたが長さ $N$ 未満の $p \in P_N$ を選び、$p$ の成分に現れない $j \in I_N$ 全体における組 $(L(p \textrm{⌒} (j)),j)$ の辞書順での最小値 $(w_p,j_p)$ を尋ねる。
2. 続いて順路大好きbotが組 $(w_p,j_p)$ を答える。

その後、先頭と末尾がそれぞれ $1, N$ である $p \in P_N$ 全体における $L(p)$ の最小値を求めてください。以下この値を $d(1,N)$ と置きます。

入出力

$p \in P_N$ とその長さ以下の正整数 $\ell$ に対し $p$ の $\ell$ 個目の成分を $p_{\ell}$ と書き表します。

整数または $\infty$ である値 $w$ に対し、$w = \infty$ ならば $w' = -1$、$w \neq \infty$ ならば $w' = w$ と定めます。

最初に $N$ が標準入力から $1$ 行で与えられます。

$N$

その後で $0$ 回以上 $N$ 回以下の好きな回数質問をしてください。質問は標準入出力を用いて以下の形式で行います：

1. まず $N$ 未満の正整数 $L$ と長さ $L$ の $p \in P_N$ を選びます。その後?と $L$ を半角空白区切りで $1$ 行に出力して改行し、$L$ 以下の正整数 $\ell$ に対する $p_{\ell}$ を $\ell$ が小さい順に半角空白区切りで $1$ 行で出力してください。

? $L$
$p_1$ $\cdots$ $p_L$

2. 続いて $w_p', i_p$ が半角空白区切りで $1$ 行で与えられます。この際のジャッジ計算量は $O(N^2)$ であることが保証されます。

$w_p'$ $i_p$

次にあなたはこの問題に対する答えを標準出力に以下の形式で出力してください：

• !と $d(1,N)'$ を半角空白区切りで $1$ 行で出力してください。

! $d(1,N)'$

最後に改行してください。

制約

入力では与えられませんが、道は以下の制約を満たします：

• どの広場を道が結ぶかやその長さは全ての質問の前に固定しており、すなわち質問の前後で変化しない。
• 道は相異なる広場を結ぶ。
• 任意の $i,j \in I_N$ に対し、広場 $i$ と広場 $j$ を結ぶ道は高々 $1$ 本である。
• 道の長さは $10$ 以下の正整数である。

入力は以下の制約を満たします：

• $N$ は $2 \leq N \leq 10$ を満たす整数である。
• 長さ $N$ 未満の任意の $p \in P_N$ に対し、$p$ の成分に現れない $j \in I_N$ 全体における組 $(L(p \textrm{⌒} (j)),j)$ の辞書順での最小値を尋ねた際の返答である入力 $w_p', j_p$ は以下を満たす。
• $w_p'$ は $w_p = -1$ または $1 \leq w_p \leq 10(N-1)$ を満たす整数である。
• $j_p$ は $1 \leq j_p \leq N$ を満たしかつ $p$ の成分に現れない整数である。

注意

リアクティブ形式の問題に慣れてない方は、リアクティブ形式の問題についてのまとめも参考にしてください。

この問題において、以下の指示に従っていない提出のジャッジ結果は保証しません：

• 出力は指定された形式に厳格に従ってください。例えば余計な空白を入れたりしないでください。
• 出力を行うたびに末尾に改行を入れて標準出力をflushしてください。
• この問題に対する答えを出力した後はプログラムをすぐに終了させてください。

サンプル

2

? 1
1

-1 2

? 1
2

-1 1

! -1

4

? 2
2 3

1 1

? 2
3 2

2 1

? 3
1 2 3

3 4

? 3
1 3 2

3 4

! 3