Detta är ett interaktivt problem.
VegiCat känner till en array $a_1, a_2, \ldots, a_n$, där varje element är $0$, $1$ eller $2$. Han vill inte berätta dess värden för dig, men du kan ställa frågor till honom. I varje fråga väljer du två index $i$ och $j$, och VegiCat berättar om $a_i > a_j$.
VegiCat ber dig att skriva ut indexen i icke-avtagande ordning efter motsvarande arrayvärden. Det vill säga, hitta en permutation $p_1, p_2, \ldots, p_n$ av $1, 2, \ldots, n$ sådan att
$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_n}.$$
Du får ställa högst $2n - 3$ frågor i varje testfall.
Interaktorn är adaptiv. Det innebär att arrayen inte är fastställd i förväg. Interaktorn garanterar att det alltid finns minst en array med element i $\{0, 1, 2\}$ som är förenlig med alla svar som getts hittills. Din slutliga permutation måste vara giltig för varje array som är förenlig med alla svar.
Indata
Den första raden innehåller ett heltal $T$ ($1 \le T \le 250$), antalet testfall. Beskrivningen av testfallen följer.
Varje testfall börjar med ett heltal $n$ ($2 \le n \le 500$), längden på arrayen.
Summan av $n$ över alla testfall överstiger inte $500$.
Interaktion
För att ställa en fråga, skriv ut en rad på följande format:
? i j
Här är $1 \le i, j \le n$. Efter varje fråga ska du läsa in ett heltal:
- $1$, om $a_i > a_j$;
- $0$, om $a_i \le a_j$.
Frågor med $i = j$ och upprepade frågor är tillåtna och räknas in i antalet frågor.
När du har bestämt ordningen, skriv ut en rad på följande format:
! p_1 p_2 ... p_n
Varje index från $1$ till $n$ måste förekomma exakt en gång. Att skriva ut svaret räknas inte som en fråga.
Om ditt svar är korrekt, gå vidare till nästa testfall genom att läsa in dess $n$, eller avsluta programmet om detta var det sista testfallet. Interaktorn skickar ingen separat bekräftelse efter ett svar.
Efter att du skrivit ut varje fråga eller svar måste du skriva ut en ny rad och tömma utdatabufferten (flush). För att tömma utdatabufferten kan du använda:
fflush(stdout)ellercout.flush()i C/C++;System.out.flush()i Java och Kotlin;sys.stdout.flush()i Python.
Om du ställer en ogiltig fråga, överskrider frågegränsen eller skriver ut ett felaktigt svar får du bedömningen Wrong Answer. Utdata som inte följer det angivna formatet bedöms också som Wrong Answer. I dessa fall avslutas interaktorn utan att skicka något felsvar.
Examples
Input 1
2 3 1 1 2 0
Output 1
? 1 2 ? 2 3 ! 3 2 1 ? 1 2 ! 1 2
Note
I det första testfallet returnerar frågorna ? 1 2 och ? 2 3 båda $1$, så $a_1 > a_2 > a_3$. Därför är $(3, 2, 1)$ ett korrekt svar.
I det andra testfallet returnerar frågan ? 1 2 värdet $0$, så $a_1 \le a_2$. Därför är $(1, 2)$ ett korrekt svar.