To jest zadanie interaktywne. Pamiętaj o opróżnianiu bufora wyjścia po każdym wypisaniu danych. Możesz użyć:

• fflush(stdout) lub cout.flush() w C/C++;
• System.out.flush() w Javie i Kotlinie;
• sys.stdout.flush() w Pythonie;
• W przypadku innych języków zajrzyj do dokumentacji.

Little Cyan Fish ma tajną permutację $p_0,p_1,\ldots,p_n$ długości $n+1$, złożoną z liczb całkowitych od $0$ do $n$. Chce, abyś ją odgadł. W tym celu Little Cyan Fish pozwala wykonać nie więcej niż $1024$ zapytania następującej postaci:

• ? i j: Otrzymaj indeks $k$ ($0\le k\le n$), dla którego $p_k=|p_i-p_j|$.

Oczywiście poprawne zapytanie wymaga, aby $i$ i $j$ były liczbami całkowitymi z przedziału $[0,n]$. Na przykład, jeśli $p_0=2,p_1=0,p_2=1$, zapytanie ? 0 2 zwróci indeks $2$, ponieważ $|p_0-p_2|=|2-1|=1=p_2$.

Little Cyan Fish chce, abyś opracował strategię znalezienia permutacji. Oczywiście nie chce, abyś wygrał zbyt łatwo. Dlatego będzie adaptacyjnie zmieniał permutację $p$, aby zastawić na ciebie pułapkę (szczegóły w sekcji „Interakcja”).

Wejście

Jest wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1\le T\le100$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$ ($1\le n\le1000$). Następnie rozpoczyna się interakcja.

Interakcja

Aby zadać zapytanie, wypisz wiersz w następującym formacie:

$$?\ i\ j$$

Tutaj $i$ i $j$ są liczbami całkowitymi od $0$ do $n$. Musisz zapewnić, że liczba zapytań nie przekroczy $1024$. W odpowiedzi otrzymasz liczbę całkowitą $k$ taką, że $p_k=|p_i-p_j|$.

Aby podać odpowiedź, wypisz wiersz w następującym formacie:

$$!\ p_0\ p_1\ \ldots\ p_n$$

Tutaj $p$ jest permutacją, którą chcesz podać.

Po wypisaniu zapytania lub odpowiedzi nie zapomnij wypisać znaku nowego wiersza i opróżnić strumienia wyjściowego.

W tym zadaniu interaktor jest adaptacyjny. Oznacza to, że permutacja $p$ może się zmieniać w zależności od twoich zapytań, o ile nie przeczy wcześniejszym zapytaniom.

Przykład

Przykładowa interakcja 1

Odczyt:

1
3

Zapis:

? 2 2

Odczyt:

1

Zapis:

? 0 3

Odczyt:

3

Zapis:

! 2 0 3 1

Narzędzie testujące: Udostępniono narzędzie pomagające uczestnikom opracowywać i testować rozwiązania. Możesz je pobrać z załączników. Uruchomienie go z opcją -h powinno wyświetlić opis użycia. Narzędzie implementuje tylko niektóre scenariusze testowe i część funkcjonalności rzeczywistego programu oceniającego.