To jest zadanie interaktywne.
VegiCat zna tablicę $a_1, a_2, \ldots, a_n$, w której każdy element jest równy $0$, $1$ lub $2$. Nie chce zdradzić Ci jej wartości, ale możesz zadawać mu pytania. W każdym zapytaniu wybierasz dwa indeksy $i$ oraz $j$, a VegiCat mówi Ci, czy $a_i > a_j$.
VegiCat prosi Cię o wypisanie indeksów w kolejności niemalejącej odpowiadających im wartości w tablicy. Innymi słowy, znajdź permutację $p_1, p_2, \ldots, p_n$ liczb $1, 2, \ldots, n$ taką, że
$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_n}.$$
W każdym przypadku testowym możesz zadać co najwyżej $2n - 3$ zapytań.
Interaktor jest adaptacyjny. Oznacza to, że tablica nie jest ustalona z góry. Interaktor gwarantuje, że zawsze istnieje co najmniej jedna tablica o elementach ze zbioru $\{0, 1, 2\}$ zgodna ze wszystkimi dotychczas udzielonymi odpowiedziami. Twoja ostateczna permutacja musi być poprawna dla każdej tablicy zgodnej ze wszystkimi odpowiedziami.
Wejście
Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 250$), oznaczającą liczbę przypadków testowych. Poniżej znajduje się opis przypadków testowych.
Każdy przypadek testowy zaczyna się od liczby całkowitej $n$ ($2 \le n \le 500$), oznaczającej długość tablicy.
Suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $500$.
Interakcja
Aby zadać zapytanie, wypisz wiersz w następującym formacie:
? i j
Tutaj $1 \le i, j \le n$. Po każdym zapytaniu wczytaj jedną liczbę całkowitą:
- $1$, jeśli $a_i > a_j$;
- $0$, jeśli $a_i \le a_j$.
Zapytania z $i = j$ oraz powtarzające się zapytania są dozwolone i wliczają się do limitu zapytań.
Gdy ustalisz już porządek, wypisz wiersz w następującym formacie:
! p_1 p_2 ... p_n
Każdy indeks od $1$ do $n$ musi pojawić się dokładnie raz. Wypisanie odpowiedzi nie jest liczone jako zapytanie.
Jeśli Twoja odpowiedź jest poprawna, przejdź do następnego przypadku testowego, wczytując jego $n$, lub zakończ działanie programu, jeśli był to ostatni przypadek testowy. Interaktor nie wysyła osobnego potwierdzenia po otrzymaniu odpowiedzi.
Po wypisaniu każdego zapytania lub odpowiedzi wypisz znak nowej linii i opróżnij bufor wyjścia (flush). Aby opróżnić bufor wyjścia, możesz użyć:
fflush(stdout)lubcout.flush()w C/C++;System.out.flush()w Javie i Kotlinie;sys.stdout.flush()w Pythonie.
Jeśli zadasz nieprawidłowe zapytanie, przekroczysz limit zapytań lub wypiszesz błędną odpowiedź, otrzymasz werdykt Wrong Answer. Wyjście niezgodne z określonym formatem również skutkuje werdyktem Wrong Answer. W takich przypadkach interaktor kończy działanie bez wysyłania komunikatu o błędzie.
Przykład
Wejście 1
2 3 1 1 2 0
Wyjście 1
? 1 2 ? 2 3 ! 3 2 1 ? 1 2 ! 1 2
Uwagi
W pierwszym przypadku testowym zapytania ? 1 2 oraz ? 2 3 zwracają $1$, zatem $a_1 > a_2 > a_3$. Dlatego $(3, 2, 1)$ jest poprawną odpowiedzią.
W drugim przypadku testowym zapytanie ? 1 2 zwraca $0$, zatem $a_1 \le a_2$. Dlatego $(1, 2)$ jest poprawną odpowiedzią.