問題文

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

パ研王国には N 個の交差点があり、1 から N までの番号が付いています。また、M 本の道があり、それぞれの道は 2 個の異なる交差点を双方向に結んでいます。2 本の異なる道が同じ交差点の組を結ぶことはありません。

これらの道には 1 以上 K 以下の整数で表される色が塗られています。複数の道が同じ色で塗られているかもしれません。ただし、ある交差点につながれた道の中に、同じ色の道が 2 本以上存在することはありません。

茜さんは、交差点を移動するロボットを開発しました。このロボットには、(1, 2, \ldots, K) を並び替えることで得られる数列 P = (P_1, P_2, \ldots, P_K) を与えて操作します。ロボットは今いる頂点につながれた道のうち、その色が P に一番最初に出現するようなものを選び、その道に沿って移動します。(追記: 12:40) この移動は 1 回の操作につき 1 度のみ行われます。

茜さんは交差点の数 N および色の種類数 K のみを知っています。そこで茜さんは以下の 調査 を最大 10000 回行うことで、道の数 M と各道がつなぐ交差点の番号、および各道の色を特定したいです。

調査: 頂点 v を選びそこにロボットを配置する。その後ロボットに P = (P_1, P_2, \ldots, P_K) を与えて操作して、ロボットの移動先の交差点の番号を調べる。

ただし、茜さんは非常に忙しいため調査の回数はできるだけ少なくしたいです。

茜さんの戦略を実装したプログラムを作成してください。

制約

• 3 \leq N \leq 500
• N - 1 \leq M \leq 500
• 2 \leq K \leq 500
• どの交差点からどの交差点へも、0 本以上の道を経由して移動できる

小課題

1. (3 点) N=3, M=2, K=2, \mathrm{subtask\_id} = 1
2. (3 点) N=3, M=2, \mathrm{subtask\_id} = 2
3. (4 点) K=2, \mathrm{subtask\_id} = 3
4. (90 点) \mathrm{subtask\_id} = 4 。この小課題では，以下に従い得点が決定される。
   • この小課題に対応するテストケースについて，1 つでも AC でない判定を得たものがあった場合、この小課題の得点は 0 点となる。
   • そうでない場合、この小課題のすべてのテストケースにおける、調査の回数の最大値を Q とする。このとき、小課題の得点は以下のように決定される。
     • 8750 < Q \leq 10000 のとき 5 点
     • 5003 < Q \leq 8750 のとき \left\lfloor\frac{20000}{Q - 4750}\right\rfloor 点
     • 5000 < Q \leq 5003 のとき 90 - (Q - 5000) \times 3 点
     • Q \leq 5000 のとき 90 点

入出力

最初に、交差点の数 N 、色の種類数 K、小課題の番号 \mathrm{subtask\_id} が以下の形式で入力で与えられる。

N K \mathrm{subtask\_id}

次に、あなたは 10000 回以下調査を行う。 v と P = (P_1, P_2, \ldots, P_K) は、標準出力に以下の形式で出力されなければならない。

? v P_1 P_2 \ldots P_K

ここで v は 1 \leq v \leq N を満たす整数である必要がある。また、(P_1, P_2, \ldots, P_K) は (1, 2, \ldots, K) を並び替えて得られる数列でなければならない。

次に、クエリの答えが標準入力から以下の形式で与えられる。

\mathrm{ans}

ここで \mathrm{ans} は 1 以上 N 以下の整数で、ロボットが移動した先の交差点の番号を表す。

最後に、答えを以下の形式で出力しなければならない。

!
M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

ここで M は道の本数、A_i と B_i は道の両端の交差点の番号、C_i は道の色を表す。

ただし、道を出力する順番、および A_i と B_i の順番は任意である。

ジャッジ

• 出力のあと、標準出力を flush しなければならない。 そうしない場合、ジャッジ結果は不定である。

• 答えを出力した後、プログラムをすぐに終了しなければならない。そうでないときの挙動は定義されていない。

• 不正な質問や不正な出力を行った場合、ジャッジ結果は不定である。

入出力例

以下の例は意味をもつやりとりとは限らない。

採点に関する注意

すべてのテストケースについて，実際の採点プログラムは適応的 (adaptive) ではない。これは、採点プログラムは初めから固定された道の情報を持つということを意味する．