問題文

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

Alice は 1 から N までの整数を並び替えた順列を隠し持っています。Alice には Bob という友達がいます。Bob は隠し事が嫌いなので、この順列を特定しようと質問してくることが予想されます。その質問をなるべくかわして特定されないようにするため、Alice は Oscar と模擬訓練を行って練習することにしました。

模擬訓練は質問フェーズと解答フェーズからなります。質問フェーズでは、Alice は順列に関するいくつかの質問に答えなければなりません。その後の解答フェーズでは、質問の解答に矛盾しない順列 a_1, a_2, \ldots, a_N を 2 つ構成しなければなりません。

質問フェーズでは、いくつかの質問が与えられるので順番に答えてください。はじめ、Oscar のスタミナ S は 2N であり、質問するたびにスタミナを消費します。質問には 3 種類あり、以下の形式で与えられます。

• タイプ 1: 3 つの相異なる整数 i,j,k が与えられる。3 つの整数 a_i,a_j,a_k の中央値となるべき整数 m を回答せよ。m は 1 以上 N 以下でなければならない。この質問をすると Oscar のスタミナ S は 2 減少する。

• タイプ 2: 2 つの異なる整数 i,j が与えられる。a_i < a_j となるべきであれば i を、a_i > a_j となるべきであれば j を回答せよ。この質問をすると Oscar のスタミナ S は 2 減少する。

• タイプ 3: 2 つの異なる整数 i,j が与えられる。a_i,a_j の最小値となるべき整数 x を回答せよ。x は 1 以上 N 以下でなければならない。この質問をすると Oscar のスタミナ S は 1 減少する。

質問には必ず答える必要があります。また、Oscar は疲れてしまうので、 質問した後に Oscar のスタミナ S が 2 以下になることはありません。

質問フェーズが終了すると、解答フェーズとなります。

解答フェーズでは、2 つの 1 から N までの整数を並び替えた順列 a_1, a_2, \ldots, a_N と b_1, b_2, \ldots, b_N を Oscar に伝えます。この 2 つの順列は、それぞれの質問フェーズでのすべての回答に矛盾しない順列であり、a_i \neq b_i となる i の個数が \left\lceil \frac{S}{2} \right\rceil 以上であれば、Oscar は混乱します。ここでの S は、Oscar がすべての質問を終えた後のスタミナです。Oscar が混乱するような 2 つの順列を伝えることができれば Alice の勝ちです。このような 2 つの順列を構成できることが証明できます。

Alice にとって Oscar が混乱するような 2 つの順列を探し出すのは非常に難しく、意気消沈してしまいました。どのような質問が来ても Oscar が混乱するような 2 つの順列を出力するプログラムを作成し、Alice を元気づけてください。

制約

• 4 \leq N \leq 5 \times 10^4
• N は整数

入出力

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

N

その後、タイプ 1,2,3 の質問、もしくは解答フェーズの開始を表す記号が入力として与えられる。

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

? 1 i j k

i,j,k は 1 から N までの相異なる整数である。

次に、質問への回答を以下の形式で出力すること。

m

m は 1 から N までの整数でなければならない。さらに、これは a_i,a_j,a_k の 3 つの整数の中央値であり、b_i,b_j,b_k の 3 つの整数の中央値である必要がある。末尾には改行を出力すること。

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

? 2 i j

i,j は 1 から N までの相異なる整数である。

次に、質問への回答を以下の形式で出力すること。

p

p は i または j の整数でなければならない。さらに、p=i であれば a_i < a_j かつ b_i < b_j、p=j であれば a_i > a_j かつ b_i > b_j である必要がある。末尾には改行を出力すること。

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

? 3 i j

i,j は 1 から N までの相異なる整数である。

次に、質問への回答を以下の形式で出力すること。

x

x は x=\min(a_i,a_j)=\min(b_i,b_j) を満たす必要がある。末尾には改行を出力すること。

解答フェーズに移るとき、以下の形式で解答フェーズの開始を表す記号が与えられる。

!

この後、 2 つの順列を以下の形式で出力すること。

a_1 a_2 \cdots a_N
b_1 b_2 \cdots b_N

Bob の残りのスタミナが S の時、順列 a_i \neq b_i となる i の個数が \left\lceil \frac{S}{2} \right\rceil 以上である必要がある。末尾には改行を出力すること。 2 つの順列を出力した後、あなたのプログラムは直ちに終了しなければならない。終了しなかった場合のジャッジ結果は不定である。

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

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

printf("%d\n", m); fflush(stdout);

C++ では

cout<<m<<endl;

と出力すればよい。

入出力例

以下のような入出力が考えられる。

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