To jest zadanie interaktywne.

Morze, znów się spotkaliśmy. Oby następne wakacje również były szczęśliwe! Bardzo dawno temu Una i Mewa były już dobrymi przyjaciółmi.

Lubiły grać w gry. Poprzednio gra wymyślona przez Unę została łatwo rozwiązana dzięki doskonałej strategii Mewy. Tym razem Una przyniosła nową grę.

Una rozważa drzewo o $n$ wierzchołkach. Mewa może zadać co najwyżej $n$ zapytań:

• Mewa może podać Unie permutację $P_1, P_2, \dots, P_n$ (gdzie $0 \le P_i \le n-1$ oraz wszystkie $P_i$ są różne). Wtedy Una mówi Mewie długość ważonej średnicy drzewa, gdy wierzchołkowi $i$ przypisano wagę $2^{P_i}$.

Czasami jednak Mewa zauważa, że Una robi problemy. Mówiąc dokładniej, zdarza się, że niezależnie od zadawanych pytań nie można jednoznacznie określić drzewa. W takich przypadkach Mewa może zgłosić, że nie ma rozwiązania.

Interakcja

To jest zadanie interaktywne. Po każdym wypisaniu należy opróżnić bufor wyjścia. Aby opróżnić bufor wyjścia, można użyć:

• C/C++: fflush(stdout) lub cout.flush()
• Java i Kotlin: System.out.flush()
• Python: sys.stdout.flush()

Najpierw wczytaj liczbę testów $T$ ($1 < T < 10^4$). Dla każdego testu wczytaj rozmiar drzewa $n$ ($2 \le n \le 100$, $\sum n^2 < 10^6$).

Aby zadać zapytanie, wypisz jedną linię w formacie "? $P_1 P_2 \dots P_n$" (gdzie $0 \le P_i \le n-1$ oraz $1 < i < j \le n$ oznacza $P_i \ne P_j$). Następnie wczytaj ciąg $n$ znaków reprezentujący wagę średnicy drzewa w zapisie binarnym. Jeżeli zapytanie jest nieprawidłowe lub w jednym teście zadano więcej niż $n$ zapytań, program oceniający wypisuje -1. Po wczytaniu -1 należy natychmiast zakończyć działanie, aby uniknąć niezdefiniowanego zachowania.

Jeżeli stwierdzisz, że nie da się jednoznacznie określić drzewa, wypisz "! NO". W przeciwnym razie wypisz jedną linię w formacie "! YES $u_1 v_1 u_2 v_2 \dots u_{n-1} v_{n-1}$" oznaczającą, że drzewo zawiera krawędzie $(u_i, v_i)$. Krawędzie można wypisać w dowolnej kolejności.

Następnie wczytaj słowo "OK" lub "WA" informujące, czy odpowiedź była poprawna. Po wczytaniu "WA" należy natychmiast zakończyć działanie, aby uniknąć niezdefiniowanego zachowania. Jeżeli wypiszesz YES, gdy drzewa nie da się jednoznacznie określić, to nawet jeśli odpowiedź jest poprawna, Una uzna, że oszukujesz, i odpowiedź zostanie uznana za błędną.

Program oceniający nie jest adaptacyjny – odpowiedź nie zmienia się po zadaniu zapytania.

Przykład

Wejście 1

2
4
1110
1110
OK
3
111
OK

Wyjście 1

? 0 1 2 3
? 2 1 0 3
! YES 1 4 2 4 3 4
? 0 1 2
! NO

Uwagi

Dostarczone jest narzędzie testowe, które pozwala uczestnikom opracowywać i testować rozwiązania. Można je pobrać z załączonych plików. Uruchomienie narzędzia z opcją "-h" wyświetli instrukcję obsługi. Narzędzie testowe implementuje tylko część funkcji rzeczywistego programu oceniającego i obsługuje tylko niektóre scenariusze testowe.