順列の復元

$Q$ は $1$ から $N$ までの整数をちょうど 1 回ずつ含む順列でなければならない。同じ順列を複数回クエリしてもよい。クエリを出力した後は、必ず出力バッファを flush すること。

各正しいクエリの後、整数 $L$ を入力として受け取る。$L$ は $R_i=P_{Q_i}$ で定義される順列 $R$ の最長サイクルの長さである。

順列 $P$ を特定できたら、次の形式で最終解答を出力する。

$!\ P_1\ P_2\ \cdots\ P_N$

最終解答の ! 出力は $1600$ 回のクエリ制限には含まれない。最終解答が隠された順列 $P$ と異なる場合は不正解となる。最終解答を出力した後も出力バッファを flush し、ただちにプログラムを終了すること。

不正なクエリを出力した場合、または ? 形式のクエリを $1600$ 回より多く行った場合、-1 を受け取ることがある。その場合はただちにプログラムを終了すること。

対話の例

$N=3$、隠された順列が $P=(2,3,1)$ の場合を考える。実際の対話では $P$ は与えられない。

• インタラクタは 3 を送る。
• 参加者は ? 1 2 3 を出力して flush する。このとき $R=(2,3,1)$ なので、インタラクタは 3 を送る。
• 参加者は ? 3 1 2 を出力して flush する。このとき $R=(1,2,3)$ なので、インタラクタは 1 を送る。
• 参加者は ! 2 3 1 を出力し、flush して終了する。

この例は通信形式と応答の意味を説明するものであり、順列を復元する一般的な方法を示すものではない。