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

Aliceは、$1$ から $N$ までの整数の順列 $a_1, a_2, \dots, a_N$ を秘密裏に作成し、Bobに $N$ を伝えます。 Bobは、この順列を特定するために質問を行います。 質問には以下の2種類があります。

• タイプ1: 「? 1 i j k」という形式。Bobは3つの異なる整数 $i, j, k$ ($1 \le i, j, k \le N$) を選び、Aliceは $a_i, a_j, a_k$ の中央値（最小でも最大でもない値）をBobに伝えます。
• タイプ2: 「? 2 i j」という形式。Bobは2つの異なる整数 $i, j$ ($1 \le i, j \le N$) を選び、Aliceは $a_i < a_j$ ならば $i$ を、そうでなければ $j$ を答えます。

このゲームはBobにとって簡単すぎるように思われたため、Aliceは新しいルールを導入しました。第一に、Bobが質問できるのはタイプ1が最大 $2N$ 回、タイプ2が最大2回までです。第二に、Aliceはこれまでの回答と矛盾しない限り、順列を自由に変更できます。 Bobが勝利し、順列を特定するプログラムを作成してください。

インタラクション

まず、ジャッジプログラムが整数 $N$ を1行で出力します ($4 \le N \le 60\,000$)。 その後、質問を行うことができます。

タイプ1の質問は「? 1 i j k」という形式の行で行います ($1 \le i, j, k \le N$; $i, j, k$ は互いに相異なる)。 ジャッジプログラムは、$a_i, a_j, a_k$ の中央値を1行で出力します。このタイプの質問は最大 $2N$ 回まで可能です。

タイプ2の質問は「? 2 i j」という形式の行で行います ($1 \le i, j \le N$; $i \neq j$)。 ジャッジプログラムは、$a_i < a_j$ ならば $i$ を、$a_i > a_j$ ならば $j$ を1行で出力します。このタイプの質問は最大2回まで可能です。

順列が特定できたら、「! a1 a2 ... aN」という形式で答えを出力してください。 インタラクションは適応的であることに注意してください。ジャッジプログラムは、これまでの回答と矛盾しない限り、いつでも順列を変更できます。特に、順列がまだ一意に定まっていない段階で答えを推測しようとすると、ジャッジプログラムは即座に別の順列を選択し、不正解とみなす可能性があります。

質問や回答を出力した後は、必ず改行を出力し、出力バッファをフラッシュしてください。そうしないと、「Idleness Limit Exceeded」エラーになる可能性があります。

入出力例

入力 1

5
4
4
2

出力 1

? 1 1 2 3
? 2 2 4
? 1 1 5 4
! 3 5 4 1 2