To zadanie interaktywne.

Sędziowie pracują nad strategią programu jurorskiego dla zmodyfikowanej wersji zadania J z bieżących zawodów.

W tym zadaniu Alice potajemnie wymyśla permutację pierwszych $N$ liczb całkowitych $a_1, a_2, \dots, a_N$ i podaje $N$ Bobowi. Bob zadaje pytania, aby zidentyfikować tę permutację. Alice może zmieniać permutację w trakcie procesu, o ile jest ona zgodna z jej poprzednimi odpowiedziami.

Sędziowie planują stworzyć AliceBot, który będzie działał w następujący sposób.

Istnieją dwie fazy: faza pytań i faza odpowiedzi.

W fazie pytań sędzia podaje AliceBot liczbę całkowitą $N$. Następnie AliceBot musi odpowiedzieć na pytania zadawane przez sędziego dotyczące permutacji.

W kolejnej fazie odpowiedzi AliceBot musi utworzyć dwie różne permutacje $a_1, \dots, a_N$ oraz $b_1, \dots, b_N$, które są zgodne z odpowiedziami z poprzedniej fazy.

Sędzia zadający pytania posiada początkową cierpliwość $P = 2N$. Każde zadane przez sędziego pytanie zmniejsza jego cierpliwość.

Sędzia może zadać trzy rodzaje pytań:

• Typ 1, sformatowany jako "? 1 i j k": sędzia wybiera trzy różne liczby całkowite $i, j, k$ ($1 \le i, j, k \le N$), AliceBot patrzy na trzy liczby $a_i, a_j$ oraz $a_k$ i podaje Bobowi wartość ich mediany (tę, która nie jest ani minimum, ani maksimum). Każde takie pytanie zmniejsza cierpliwość sędziego o 2.
• Typ 2, sformatowany jako "? 2 i j": sędzia wybiera dwie różne liczby całkowite $i, j$ ($1 \le i, j \le N$) i AliceBot odpowiada $i$, jeśli $a_i < a_j$, lub $j$ w przeciwnym razie. Każde takie pytanie zmniejsza cierpliwość sędziego o 2.
• Typ 3, sformatowany jako "? 3 i j": sędzia wybiera dwie różne liczby całkowite $i, j$ ($1 \le i, j \le N$) i AliceBot podaje minimalną wartość spośród $a_i$ oraz $a_j$. Każde takie pytanie zmniejsza cierpliwość sędziego o 1.

Możesz założyć, że cierpliwość sędziego nigdy nie spadnie poniżej 2 po zadaniu pytania. Gdy sędzia uzna, że zadał wystarczającą liczbę pytań, do AliceBot wysyłana jest komenda "!", co przełącza go w fazę odpowiedzi.

W fazie odpowiedzi AliceBot podaje sędziemu dwie permutacje $a_1, \dots, a_N$ oraz $b_1, \dots, b_N$. Te dwie permutacje muszą być zgodne ze wszystkimi odpowiedziami udzielonymi w fazie pytań, a liczba pozycji $i$, dla których $a_i \neq b_i$, musi wynosić co najmniej $\lceil p/2 \rceil$, gdzie $p$ to cierpliwość sędziego na koniec fazy pytań.

Ponieważ sędzia jest zbyt leniwy, Twoim zadaniem jest zaimplementowanie AliceBot. Można wykazać, że problem jest rozwiązywalny dla każdego możliwego $N$ z podanych ograniczeń.

Interakcja

Najpierw program jurorski podaje liczbę całkowitą $N$ w osobnej linii ($4 \le N \le 50\,000$).

Następnie sędzia zadaje pytania.

Pytanie typu 1 to linia sformatowana jako "? 1 i j k" ($1 \le i, j, k \le N$; $i, j$ oraz $k$ są parami różne). Następnie wypisujesz linię z pojedynczą liczbą całkowitą: medianą wartości $a_i, a_j$ oraz $a_k$.

Pytanie typu 2 to linia sformatowana jako "? 2 i j" ($1 \le i, j \le N$; $i \neq j$). Następnie wypisujesz linię z pojedynczą liczbą całkowitą: $i$, jeśli $a_i < a_j$, lub $j$, jeśli $a_i > a_j$.

Pytanie typu 3 to linia sformatowana jako "? 3 i j" ($1 \le i, j \le N$; $i \neq j$). Następnie wypisujesz linię z pojedynczą liczbą całkowitą: minimalną wartość spośród $a_i$ oraz $a_j$.

Niech $q_1$ oznacza łączną liczbę pytań typu 1, $q_2$ liczbę pytań typu 2, a $q_3$ liczbę pytań typu 3. Możesz założyć, że wartość $p = 2N - 2q_1 - 2q_2 - q_3$ nie jest mniejsza niż 2.

Aby przejść do fazy odpowiedzi, program jurorski wysyła linię zawierającą znak "!". Następnie musisz wypisać dwie linie: pierwszą zawierającą $N$ liczb całkowitych oddzielonych spacjami $a_1, \dots, a_N$ oraz drugą zawierającą $N$ liczb całkowitych oddzielonych spacjami $b_1, \dots, b_N$. Każda z tych dwóch sekwencji musi być permutacją liczb $1, \dots, N$ i muszą one różnić się na co najmniej $\lceil p/2 \rceil$ pozycjach.

Nie zapomnij wypisać znaku nowej linii i opróżnić bufora wyjściowego po wypisaniu odpowiedzi oraz po wypisaniu każdej permutacji, w przeciwnym razie możesz otrzymać błąd "Idleness Limit Exceeded".

Przykład

Wejście 1

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

Wyjście 1

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