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

심사위원들은 현재 대회의 문제 J의 수정된 버전을 위한 심사 프로그램 전략을 작업 중입니다.

해당 문제에서, 앨리스는 비밀리에 첫 $N$개의 정수의 순열 $a_1, a_2, \dots, a_N$을 만들고 밥에게 $N$을 알려줍니다. 밥은 이 순열을 알아내기 위해 몇 가지 질문을 합니다. 앨리스는 이전 답변들과 모순되지 않는 한 과정 중에 순열을 변경할 수 있습니다.

심사위원들은 다음을 수행할 AliceBot을 만들 계획입니다. 두 단계가 있습니다: 질문 단계와 답변 단계.

질문 단계에서, 심사위원은 AliceBot에게 정수 $N$을 알려줍니다. 그러면 AliceBot은 심사위원이 순열에 대해 묻는 질문에 답해야 합니다.

이어지는 답변 단계에서, AliceBot은 이전 단계의 답변들과 일관된 두 개의 서로 다른 순열 $a_1, \dots, a_N$과 $b_1, \dots, b_N$을 구성해야 합니다.

심사위원이 질문을 할 때마다 심사위원의 인내심 $P$가 감소합니다. 초기 인내심은 $P = 2N$입니다.

심사위원이 할 수 있는 질문은 세 가지 유형이 있습니다:

• 유형 1, 형식 “? 1 i j k”: 심사위원은 세 개의 서로 다른 정수 $i, j, k$ ($1 \le i, j, k \le N$)를 선택하고, AliceBot은 세 정수 $a_i, a_j, a_k$를 살펴본 뒤 그중 중앙값(최솟값도 최댓값도 아닌 값)을 밥에게 알려줍니다. 이러한 각 질문은 심사위원의 인내심을 2만큼 감소시킵니다.
• 유형 2, 형식 “? 2 i j”: 심사위원은 두 개의 서로 다른 정수 $i, j$ ($1 \le i, j \le N$)를 선택하고, AliceBot은 $a_i < a_j$이면 $i$를, 그렇지 않으면 $j$를 답합니다. 이러한 각 질문은 심사위원의 인내심을 2만큼 감소시킵니다.
• 유형 3, 형식 “? 3 i j”: 심사위원은 두 개의 서로 다른 정수 $i, j$ ($1 \le i, j \le N$)를 선택하고, AliceBot은 $a_i$와 $a_j$ 중 최솟값을 알려줍니다. 이러한 각 질문은 심사위원의 인내심을 1만큼 감소시킵니다.

질문 후 심사위원의 인내심은 2 아래로 떨어지지 않는다고 가정할 수 있습니다. 심사위원이 충분한 질문을 했다고 판단하면, “!” 명령이 AliceBot에게 전송되어 답변 단계로 전환됩니다.

답변 단계에서, AliceBot은 심사위원에게 두 개의 순열 $a_1, \dots, a_N$과 $b_1, \dots, b_N$을 알려줍니다. 이 두 순열은 질문 단계에서 주어진 모든 답변과 일관되어야 하며, $a_i \neq b_i$인 위치 $i$의 개수는 질문 단계 종료 시 심사위원의 인내심을 $p$라고 할 때 최소 $\lceil p/2 \rceil$개여야 합니다.

심사위원이 너무 게으르기 때문에, 여러분은 AliceBot을 구현해야 합니다. 이 문제는 제한 사항 내의 모든 가능한 $N$에 대해 해결 가능함이 증명되어 있습니다.

인터랙션

먼저, 심사 프로그램이 별도의 줄에 정수 $N$ ($4 \le N \le 50\,000$)을 알려줍니다.

그다음 심사위원이 질문을 합니다.

유형 1 질문은 “? 1 i j k” ($1 \le i, j, k \le N$; $i, j, k$는 서로 다름) 형식의 한 줄입니다. 그러면 여러분은 $a_i, a_j, a_k$ 값의 중앙값인 정수 하나를 한 줄에 출력합니다.

유형 2 질문은 “? 2 i j” ($1 \le i, j \le N$; $i \neq j$) 형식의 한 줄입니다. 그러면 여러분은 $a_i < a_j$이면 $i$를, $a_i > a_j$이면 $j$를 정수 하나로 출력합니다.

유형 3 질문은 “? 3 i j” ($1 \le i, j \le N$; $i \neq j$) 형식의 한 줄입니다. 그러면 여러분은 $a_i$와 $a_j$ 중 최솟값인 정수 하나를 한 줄에 출력합니다.

유형 1 질문이 $q_1$개, 유형 2 질문이 $q_2$개, 유형 3 질문이 $q_3$개 있다고 합시다. $p = 2N - 2q_1 - 2q_2 - q_3$ 값은 2 이상이라고 가정할 수 있습니다.

답변 단계로 전환하기 위해, 심사 프로그램은 ‘!’ 기호로 구성된 줄을 출력합니다. 그 후, 여러분은 두 줄을 출력해야 합니다. 첫 번째 줄에는 $N$개의 공백으로 구분된 정수 $a_1, \dots, a_N$을, 두 번째 줄에는 $N$개의 공백으로 구분된 정수 $b_1, \dots, b_N$을 출력합니다. 이 두 수열은 각각 $1, \dots, N$의 순열이어야 하며, 최소 $\lceil p/2 \rceil$개의 위치에서 서로 달라야 합니다.

답변을 출력한 후에는 개행 문자를 출력하고 출력 버퍼를 비우는 것을 잊지 마십시오. 그렇지 않으면 “Idleness Limit Exceeded” 오류가 발생할 수 있습니다.

예제

입력 1

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

출력 1

4
4
1
3 5 4 1 2
5 4 3 2 1