시간 제한메모리 제한제출정답맞은 사람정답 비율
15 초 512 MB21150.000%

문제

This is an interactive problem.

Alice secretly invents a permutation of first $N$ integers $a_1, a_2, \ldots a_N$ and tells $N$ to Bob.

Bob asks questions to identify this permutation. 

He may ask questions of two types:

  • Type 1, formatted as "? 1 i j k": Bob chooses three different integers $i$, $j$, $k$ ($1 \le i, j, k \le N$), Alice looks at the three integers $a_i$, $a_j$, and $a_k$, and tells Bob the value of their median (the one that is neither minimum nor maximum).
  • Type 2, formatted as "? 2 i j": Bob chooses two different integers $i$, $j$ ($1 \le i, j \le N$), and Alice answers $i$ if $a_i < a_j$, or $j$ otherwise.

The game seems to be too easy for Bob, so Alice invented new rules. First, Bob may ask only $2 N$ questions of type 1 and only $2$ questions of type 2. Second, Alice may change the permutation freely as long as it is consistent with all answers that were given before.

Help Bob to win and write the program that identifies the permutation.

인터랙션

First, the jury program tells you one integer $N$ on a separate line ($4 \le N \le 60\,000$).

Then you may ask questions. 

A question of type 1 is a line formatted as "? 1 i j k" ($1 \le i, j, k \le N$; $i$, $j$, and $k$ are pairwise distinct). The jury program then prints a line with a single integer: the median of the values $a_i$, $a_j$, and $a_k$. You may ask a question of this type no more than $2N$ times.

A question of type 2 is a line formatted as "? 2 i j" ($1 \le i, j \le N$; $i \ne j$). The jury program then prints a line with a single integer: $i$ if $a_i < a_j$, or $j$ if $a_i > a_j$. You may ask a question of this type no more than twice.

When the permutation is uniquely determined, print the answer on a line formatted as "! a1 a2 ... aN".

Note that interaction is adaptive: the jury program may change the permutation anytime as long as it is consistent with past answers. In particular, if you are trying to guess the answer when it is not yet uniquely determined, the jury program may immediately pick another one and say you were wrong.

Don't forget to print the newline character and flush the output buffer after printing a question or an answer, otherwise, you may get the "Idleness Limit Exceeded" error.

예제 입력 1

5

4

4

2

예제 출력 1


? 1 1 2 3

? 2 2 4

? 1 1 5 4

! 3 5 4 1 2

채점 및 기타 정보

  • 예제는 채점하지 않는다.