これはインタラクティブな問題です。
審査員は、現在のコンテストにおける問題 J の修正版に対する審査員プログラムの戦略を検討しています。
その問題では、Alice が $1$ から $N$ までの整数の順列 $a_1, a_2, \dots, a_N$ を秘密裏に作成し、Bob に $N$ を伝えます。Bob はこの順列を特定するためにいくつかの質問をします。Alice は、これまでの回答と矛盾しない限り、途中で順列を変更しても構いません。
審査員は、以下を行う AliceBot を作成しようとしています。 フェーズは質問フェーズと回答フェーズの2つです。
質問フェーズでは、審査員が AliceBot に整数 $N$ を伝えます。その後、AliceBot は審査員が順列について行う質問に回答しなければなりません。
続く回答フェーズでは、AliceBot は、これまでのフェーズでの回答と矛盾しない2つの異なる順列 $a_1, \dots, a_N$ と $b_1, \dots, b_N$ を構成しなければなりません。
質問を行う審査員の初期忍耐度は $P = 2N$ です。審査員が質問をするたびに、審査員の忍耐度は減少します。
審査員が行う質問には3つのタイプがあります。
- タイプ 1: 「
? 1 i j k」という形式。審査員は3つの異なる整数 $i, j, k$ ($1 \le i, j, k \le N$) を選びます。AliceBot は3つの整数 $a_i, a_j, a_k$ を見て、その中央値（最小でも最大でもない値）を Bob に伝えます。この質問ごとに、審査員の忍耐度は 2 減少します。 - タイプ 2: 「
? 2 i j」という形式。審査員は2つの異なる整数 $i, j$ ($1 \le i, j \le N$) を選びます。AliceBot は $a_i < a_j$ ならば $i$ を、そうでなければ $j$ を回答します。この質問ごとに、審査員の忍耐度は 2 減少します。 - タイプ 3: 「
? 3 i j」という形式。審査員は2つの異なる整数 $i, j$ ($1 \le i, j \le N$) を選びます。AliceBot は $a_i$ と $a_j$ のうち小さい方の値を伝えます。この質問ごとに、審査員の忍耐度は 1 減少します。
質問をした後、審査員の忍耐度が 2 未満になることはないと仮定して構いません。審査員が十分な質問をしたと判断すると、「!」というコマンドが AliceBot に送られ、回答フェーズに切り替わります。
回答フェーズでは、AliceBot は審査員に2つの順列 $a_1, \dots, a_N$ と $b_1, \dots, b_N$ を伝えます。これら2つの順列は、質問フェーズで行われたすべての回答と矛盾してはならず、かつ $a_i \neq b_i$ となる位置 $i$ の個数が、質問フェーズ終了時の審査員の忍耐度を $p$ としたとき、少なくとも $\lceil p/2 \rceil$ 個存在しなければなりません。
審査員は非常に怠惰であるため、あなたには AliceBot を実装することが求められます。この問題は、制約下のあらゆる $N$ に対して解けることが示せます。
インタラクション
まず、審査員プログラムが整数 $N$ を別の行に出力します ($4 \le N \le 50\,000$)。
次に、審査員が質問を行います。
タイプ 1 の質問は「? 1 i j k」という形式の行です ($1 \le i, j, k \le N$; $i, j, k$ は互いに異なる)。これに対し、あなたは $a_i, a_j, a_k$ の中央値を単一の整数として出力します。
タイプ 2 の質問は「? 2 i j」という形式の行です ($1 \le i, j \le N$; $i \neq j$)。これに対し、あなたは $a_i < a_j$ ならば $i$ を、そうでなければ $j$ を単一の整数として出力します。
タイプ 3 の質問は「? 3 i j」という形式の行です ($1 \le i, j \le N$; $i \neq j$)。これに対し、あなたは $a_i$ と $a_j$ のうち小さい方の値を単一の整数として出力します。
タイプ 1 の質問回数を $q_1$、タイプ 2 の質問回数を $q_2$、タイプ 3 の質問回数を $q_3$ とします。値 $p = 2N - 2q_1 - 2q_2 - q_3$ は 2 以上であると仮定して構いません。
回答フェーズに切り替えるため、審査員プログラムは「!」という記号からなる行を出力します。その後、あなたは2行を出力しなければなりません。1行目には $N$ 個の空白区切りの整数 $a_1, \dots, a_N$ を、2行目には $N$ 個の空白区切りの整数 $b_1, \dots, b_N$ を出力します。これら2つの数列はそれぞれ $1, \dots, N$ の順列でなければならず、少なくとも $\lceil p/2 \rceil$ 個の位置で異なっていなければなりません。
回答を出力した後、および各順列を出力した後は、改行文字を出力して出力バッファをフラッシュすることを忘れないでください。そうしないと、「Idleness Limit Exceeded」エラーが発生する可能性があります。
入出力例
入出力例 1
5 ? 1 1 2 3 ? 2 2 4 ? 3 4 5 !
4 4 1 3 5 4 1 2 5 4 3 2 1