이 문제는 인터랙티브 문제입니다.

Alice는 비밀리에 첫 $N$개의 정수 $a_1, a_2, \dots, a_N$의 순열을 만들고 Bob에게 $N$을 알려줍니다. Bob은 이 순열을 알아내기 위해 질문을 합니다. Bob은 두 가지 유형의 질문을 할 수 있습니다.

• 유형 1, 형식: "? 1 i j k": Bob은 서로 다른 세 정수 $i, j, k$ ($1 \le i, j, k \le N$)를 선택합니다. Alice는 세 정수 $a_i, a_j, a_k$를 확인하고 그중 중앙값(최솟값도 최댓값도 아닌 값)을 Bob에게 알려줍니다.
• 유형 2, 형식: "? 2 i j": Bob은 서로 다른 두 정수 $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$ ($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$의 중앙값인 정수 하나를 한 줄에 출력합니다. 이 유형의 질문은 최대 $2N$번까지 할 수 있습니다.

유형 2 질문은 "? 2 i j" ($1 \le i, j \le N$; $i \neq j$) 형식의 한 줄입니다. 심사위원 프로그램은 $a_i < a_j$이면 $i$를, $a_i > a_j$이면 $j$를 정수 하나로 출력합니다. 이 유형의 질문은 최대 2번까지 할 수 있습니다.

순열이 유일하게 결정되면 "! $a_1$ $a_2$ $\dots$ $a_N$" 형식으로 답을 출력합니다. 인터랙션은 적응형(adaptive)이라는 점에 유의하세요. 심사위원 프로그램은 과거의 답변과 일치하는 한 언제든지 순열을 변경할 수 있습니다. 특히, 순열이 아직 유일하게 결정되지 않았는데 답을 추측하려고 하면, 심사위원 프로그램은 즉시 다른 순열을 선택하고 틀렸다고 할 수 있습니다.

질문이나 답을 출력한 후에는 개행 문자를 출력하고 출력 버퍼를 비우는(flush) 것을 잊지 마세요. 그렇지 않으면 "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