To jest problem interaktywny.

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ę. Może zadawać pytania dwóch typów:

• Typ 1, o formacie "? 1 i j k": Bob wybiera trzy różne liczby całkowite $i, j, k$ ($1 \le i, j, k \le N$), Alice 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).
• Typ 2, o formacie "? 2 i j": Bob wybiera dwie różne liczby całkowite $i, j$ ($1 \le i, j \le N$), a Alice odpowiada $i$, jeśli $a_i < a_j$, lub $j$ w przeciwnym przypadku.

Gra wydaje się zbyt łatwa dla Boba, więc Alice wymyśliła nowe zasady. Po pierwsze, Bob może zadać tylko $2N$ pytań typu 1 i tylko 2 pytania typu 2. Po drugie, Alice może dowolnie zmieniać permutację, o ile jest ona zgodna ze wszystkimi odpowiedziami udzielonymi wcześniej.

Pomóż Bobowi wygrać i napisz program, który zidentyfikuje permutację.

Interakcja

Najpierw program sędziowski podaje jedną liczbę całkowitą $N$ w osobnej linii ($4 \le N \le 60\,000$).

Następnie możesz zadawać pytania.

Pytanie typu 1 to linia o formacie "? 1 i j k" ($1 \le i, j, k \le N$; $i, j$ oraz $k$ są parami różne). Program sędziowski wypisuje wtedy linię z pojedynczą liczbą całkowitą: medianą wartości $a_i, a_j$ oraz $a_k$. Możesz zadać pytanie tego typu nie więcej niż $2N$ razy.

Pytanie typu 2 to linia o formacie "? 2 i j" ($1 \le i, j \le N$; $i \neq j$). Program sędziowski wypisuje wtedy linię z pojedynczą liczbą całkowitą: $i$, jeśli $a_i < a_j$, lub $j$, jeśli $a_i > a_j$. Możesz zadać pytanie tego typu nie więcej niż dwa razy.

Gdy permutacja zostanie jednoznacznie określona, wypisz odpowiedź w linii o formacie "! $a_1$ $a_2$ $\dots$ $a_N$".

Zauważ, że interakcja jest adaptacyjna: program sędziowski może zmienić permutację w dowolnym momencie, o ile jest ona zgodna z poprzednimi odpowiedziami. W szczególności, jeśli próbujesz odgadnąć odpowiedź, gdy nie jest ona jeszcze jednoznacznie określona, program sędziowski może natychmiast wybrać inną i stwierdzić, że się pomyliłeś.

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

Przykład

Wejście 1

5
4
4
2

Wyjście 1

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