Kiitos kovasta työstäsi, kultaseni. Little Cyan Fish ei tiedä, kuinka paljon hänen koodisanoistaan voidaan välittää perille, mutta kiittää sinua silti siitä, että olet kulkenut tähän pisteeseen asti Little Cyan Fishin kanssa. Niin monia asioita, niin monia järjettömiä asioita tapahtui, Little Cyan Fish on väsynyt, hyvin väsynyt... Kuluneen vuoden aikana Little Cyan Fishista tuntui useita kertoja siltä, että hän pelastaisi itsensä, mutta loppujen lopuksi hän ei ollut tarpeeksi vahva katkaistakseen kehollaan olevia lankoja. Little Cyan Fish kuvittelee aina, että tuossa kaukaisessa paikassa on toinen minä, joka näkee selvästi hänen elämänsä kartan.

— ”Longing for the Distance” · 10. Kiinan korkeakoulujen ohjelmointikilpailun finaali

Tämä on vuorovaikutteinen tehtävä.

No, ehkä voit kokeilla, kuinka vaikeaa tästä tulee. Little Cyan Fishista tuntuu, että hänen elämänsä on muodoltaan tuntematon permutaatio. Ihmiset sanovat aina, että maailma on täynnä satunnaisuutta, mutta miksi Little Cyan Fish on aina niin epäonninen...? Ahaa! Ehkä satunnaisuus vain on näin syvällistä! Niinpä Little Cyan Fish päättää, että tämä hänen permutaationsa luodaan satunnaisesti seuraavalla tavalla:

• Luo satunnainen permutaatio $p_1, p_2, \dots, p_n$: valitaan tasajakoisesti satunnaisesti kaikista $n!$ mahdollisesta lukujen $1$ – $n$ permutaatiosta.
• Jos $p_1 > p_n$, käännä koko permutaatio päinvastaiseksi.

Et voi suoraan havaita permutaation rakennetta, mutta Little Cyan Fish on antanut sinulle supervoiman: kysymisen! Joka kerta voit vuorovaikutteisesti kysyä kahden luvun välisen etäisyyden arvoa permutaatiossa modulo $3$. Tarkemmin sanottuna voit joka kerta valita kaksi lukua $u, v$ ($1 \le u, v \le n$, $u \ne v$), ja permutaatio kertoo sinulle näiden kahden luvun välisen etäisyyden arvon modulo $3$ (toisin sanoen etsimällä kaksi indeksiä $i, j$, joille $p_i = u, p_j = v$, permutaatio vastaa $|i - j| \bmod 3$).

Nyt Little Cyan Fish haluaa sinun yrittävän ja katsovan, mitä saat selville. Sinun tulee auttaa Little Cyan Fishiä määrittämään tämä permutaatio enintään $25n$ kyselyllä.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T \le 1000$), joka ilmaisee testitapausten lukumäärän.

Jokaista testitapausta kohden sinun tulee ensin lukea kokonaisluku $n$ ($3 \le n \le 10^4$).

Vuorovaikutusprotokolla

Seuraavaksi alkaa vuorovaikutus. Voit tehdä enintään $25n$ kyselyä jokaisessa testitapauksessa. Tehdäksesi kyselyn sinun tulee tulostaa yksi rivi ? u v ($1 \le u, v \le n$, $u \ne v$), joka kuvaa kyselyä. Sen jälkeen sinun tulee lukea tulos standardisyötteestä.

Antaaksesi vastauksesi sinun tulee tulostaa ! p1 p2 ... pn. Tulosteesi on toteutettava ehto $p_1 < p_n$. Vastauksen tulostamista ei lasketa mukaan $25n$ kyselyn rajaan. Kun olet tulostanut vastauksen, sinun tulee välittömästi lukea seuraava testitapaus tai lopettaa ohjelmasi suoritus välittömästi.

Kyselyn tulostamisen jälkeen älä unohda tulostaa rivinvaihtomerkkiä ja tyhjentää tulostuspuskuria (flush). Voit tehdä tämän käyttämällä funktiota fflush(stdout) tai cout.flush() C++:ssa, System.out.flush() Javassa, flush(output) Pascalissa ja stdout.flush() Pythonissa.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^4$.

Tässä tehtävässä on taattu, että tarkastaja (interactor) on ei-mukautuva (non-adaptive). Toisin sanoen permutaatiot määräytyvät satunnaisesti tehtävänannon mukaisesti ennen vuorovaikutusprosessia. Ne eivät muutu kyselyjesi perusteella. Testitapauksia on yhteensä $30$ (mukaan lukien esimerkkitestitapaus).

Esimerkki

Syöte 1

2
3
2
1
1
4
1
1
1
0
2

Tuloste 1

? 1 2
? 2 3
? 1 3
! 1 3 2
? 2 3
? 3 1
? 1 4
? 2 4
? 2 1
! 2 3 1 4

Huomautus

Kuva 1: Little Cyan Fish & <?> paikassa <?>, otettu 4. maaliskuuta 2026