Tämä on vuorovaikutteinen tehtävä.
VegiCat tietää taulukon $a_1, a_2, \ldots, a_n$, jonka jokainen alkio on $0$, $1$ tai $2$. Hän ei halua kertoa sen arvoja sinulle suoraan, mutta voit esittää hänelle kysymyksiä. Jokaisessa kyselyssä valitset kaksi indeksiä $i$ ja $j$, ja VegiCat kertoo sinulle, päteekö $a_i > a_j$.
VegiCat pyytää sinua tulostamaan indeksit vastaavien taulukon arvojen mukaisessa ei-vähenevässä järjestyksessä. Toisin sanoen, etsi lukujen $1, 2, \ldots, n$ permutaatio $p_1, p_2, \ldots, p_n$, jolle
$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_n}.$$
Voit tehdä korkeintaan $2n - 3$ kyselyä jokaisessa testitapauksessa.
Vuorovaikutusohjelma (interactor) on mukautuva (adaptive). Tämä tarkoittaa, että taulukkoa ei ole kiinnitetty etukäteen. Vuorovaikutusohjelma takaa, että on aina olemassa vähintään yksi taulukko, jonka alkiot kuuluvat joukkoon $\{0, 1, 2\}$ ja joka on ristiriidaton kaikkien tähän mennessä annettujen vastausten kanssa. Lopullisen permutaatiosi on oltava kelvollinen jokaiselle kaikkien vastausten kanssa ristiriidattomalle taulukolle.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 250$), testitapausten lukumäärän. Seuraavaksi esitetään testitapausten kuvaukset.
Jokainen testitapaus alkaa kokonaisluvulla $n$ ($2 \le n \le 500$), joka on taulukon pituus.
Lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $500$.
Vuorovaikutus
Tehdäksesi kyselyn tulosta rivi seuraavassa muodossa:
? i j
Tässä $1 \le i, j \le n$. Lue jokaisen kyselyn jälkeen yksi kokonaisluku:
- $1$, jos $a_i > a_j$;
- $0$, jos $a_i \le a_j$.
Kyselyt, joissa $i = j$, sekä toistetut kyselyt ovat sallittuja ja ne lasketaan mukaan kyselyiden määrään.
Kun olet selvittänyt järjestyksen, tulosta rivi seuraavassa muodossa:
! p_1 p_2 ... p_n
Jokaisen indeksin väliltä $1$–$n$ on esiinnyttävä täsmälleen kerran. Vastauksen tulostamista ei lasketa kyselyksi.
Jos vastauksesi on oikein, siirry seuraavaan testitapaukseen lukemalla sen $n$, tai lopeta ohjelman suoritus, jos tämä oli viimeinen testitapaus. Vuorovaikutusohjelma ei lähetä erillistä vahvistusta vastauksen jälkeen.
Jokaisen kyselyn tai vastauksen tulostamisen jälkeen tulosta rivinvaihto ja tyhjennä tulostuspuskuri (flush). Tulostuspuskurin tyhjentämiseen voit käyttää:
fflush(stdout)taicout.flush()kielissä C/C++;System.out.flush()kielissä Java ja Kotlin;sys.stdout.flush()kielessä Python.
Jos teet virheellisen kyselyn, ylität kyselyrajan tai tulostat väärän vastauksen, saat tuomion Wrong Answer. Myös tuloste, joka ei noudata määriteltyä muotoa, tuomitaan Wrong Answer -tulokseksi. Näissä tapauksissa vuorovaikutusohjelma päättyy lähettämättä virhevastausta.
Examples
Input 1
2 3 1 1 2 0
Output 1
? 1 2 ? 2 3 ! 3 2 1 ? 1 2 ! 1 2
Note
Ensimmäisessä testitapauksessa kyselyt ? 1 2 ja ? 2 3 palauttavat molemmat arvon $1$, joten $a_1 > a_2 > a_3$. Näin ollen $(3, 2, 1)$ on oikea vastaus.
Toisessa testitapauksessa kysely ? 1 2 palauttaa arvon $0$, joten $a_1 \le a_2$. Näin ollen $(1, 2)$ on oikea vastaus.