問題文

これはインタラクティブな要素がある問題です。

Alice は 1 から N までの整数を並び替えた順列 a_1, a_2, \ldots, a_N を隠し持っています。隠し事が嫌いな Bob はなんとかしてこの順列を特定したいです。できるだけこの順列を隠したい Alice は順列のサイズ N と以下の 2 つのタイプの質問の答えのみを教えてくれます。

• タイプ 1: 3 つの異なる整数 i,j,k(1 \leq i,j,k \leq N) を選び、Alice に聞きます。すると、Alice は a_i,a_j,a_k の 3 つの整数の中央値を答えます。
• タイプ 2: 2 つの異なる整数 i,j(1 \leq i,j \leq N) を選び、Alice に聞きます。すると、Alice は a_i, a_j の小さい方の添え字を答えます。つまり、a_i < a_j であれば i, そうでなければ j を答えます。

ただし、Alice はあまり順列の情報を与えたくないので、タイプ 1 の質問には 2N 回、タイプ 2 の質問には 2 回しか答えません。さらに、Alice はいじわるなので、Bob のこれまでの質問に対する返答に矛盾しない範囲で順列の並びを途中で変えてしまうかもしれません。

Bob はとても忙しいので、熟考して質問することができません。Bob の代わりに、質問をして順列を当てるプログラムを作成し、彼を助けてください。

制約

• 4 \leq N \leq 6 \times 10^4

部分点

• タイプ 1 の質問の上限は 3N 回、タイプ 2 の質問の上限は 3 回である。この上限を超えて質問をした場合は Query Limit Exceeded となる。
• 質問回数が上限を超えず、かつ正しい順列を出力したとき、20 点が得られる。
• タイプ 1 の質問が 2N 回以内、かつタイプ 2 の質問が 2 回以内であり、さらに正しい順列を出力したとき、満点が得られる。

入出力

最初に順列のサイズ N が 1 行で与えられる。

N

タイプ 1 の質問をするときは次の形式に従って出力すること。

? 1 i j k

i,j,k は 1 から N までの相異なる整数でなければならない。末尾には改行を出力すること。

タイプ 1 の質問の答えは以下の形式で与えられる。

m

m は 1 から N までの整数である。これは a_i,a_j,a_k の 3 つの整数の中央値である。

タイプ 2 の質問をするときは次の形式に従って出力すること。

? 2 i j

i,j は 1 から N までの相異なる整数でなければならない。末尾には改行を出力すること。

タイプ 2 の質問の答えは以下の形式で与えられる。

k

k は i または j である。a_i < a_j であれば i, そうでなければ j が出力される。

タイプ 1 の質問の上限は 3N 回、タイプ 2 の質問の上限は 3 回である。この上限を超えて質問をした場合は Query Limit Exceeded となる。

質問を何回かした後、順列を当てる必要がある。その際は次の形式に従って出力すること。

! a_1 a_2 a_3 \cdots a_N

順列を出力した後、あなたのプログラムは直ちに終了しなければならない。終了しなかった場合のジャッジ結果は不定である。

また、これら以外のフォーマットで出力した場合のジャッジ結果も不定である。

各出力の後には、出力をフラッシュする必要があることに注意せよ。例えば、タイプ 1 の質問をする際、 C では

printf("? 1 %d %d %d\n", i, j, k); fflush(stdout);

C++ では

cout<<"? 1 "<<i<<" "<<j<<" "<<k<<endl;

と出力すればよい。

順列は最初から固定されていないテストケースがあるので注意せよ。

入出力例

順列が "3,5,4,1,2" である場合に、以下のような入出力が考えられる。

これは入出力の一つの例であり、意味のある入出力をしているとは限らない。