Takk fyrir erfiðið þitt, elskan. Little Cyan Fish veit ekki hversu mikið af dulmálsorðum hans kemst til skila, en þakkar þér samt fyrir að hafa gengið alla þessa leið með Little Cyan Fish. Svo margt, svo margt fáránlegt gerðist, Little Cyan Fish er þreyttur, mjög þreyttur... Á liðnu ári fannst Little Cyan Fish nokkrum sinnum að hann væri að fara að bjarga sjálfum sér, en þegar öllu var á botninn hvolft var hann ekki nógu sterkur til að klippa á þræðina á líkama sínum. Little Cyan Fish ímyndar sér alltaf að á þessum fjarlæga stað sé annað sjálf sem getur séð kortið af lífi hans skýrt.

— „Longing for the Distance“ · Úrslit 10. háskólakeppninnar í forritun í Kína

Þetta er gagnvirkt dæmi.

Jæja, kannski geturðu prófað og séð hversu erfitt þetta verður. Little Cyan Fish finnst líf sitt vera umröðun af óþekktri lögun. Fólk segir alltaf að heimurinn sé fullur af tilviljunum, en hvers vegna er Little Cyan Fish alltaf svona óheppinn...? Aha! Kannski eru tilviljanir bara svona djúpstæðar! Þannig að Little Cyan Fish ákveður að þessi umröðun hans verði búin til af handahófi á eftirfarandi hátt:

• Búðu til slembna umröðun $p_1, p_2, \dots, p_n$: valin jafndreift af handahófi úr öllum $n!$ mögulegum umröðunum á $1$ til $n$.
• Ef $p_1 > p_n$, snúðu þá allri umröðuninni við.

Þú getur ekki séð byggingu umröðunarinnar beint, en Little Cyan Fish hefur gefið þér ofurkraft: að spyrja! Í hvert skipti geturðu spurt gagnvirkt um gildi fjarlægðarinnar milli tveggja talna í umröðuninni modulo $3$. Nánar tiltekið geturðu í hvert skipti valið tvær tölur $u, v$ ($1 \le u, v \le n$, $u \ne v$), og umröðunin mun segja þér gildi fjarlægðarinnar milli þessara tveggja talna modulo $3$ (þ.e. finnur tvo vísa $i, j$ sem uppfylla $p_i = u, p_j = v$ og umröðunin svarar $|i - j| \bmod 3$).

Nú vill Little Cyan Fish að þú prófir og sjáir hvað þú getur fengið. Þú þarft að hjálpa Little Cyan Fish að ákvarða þessa umröðun í ekki fleiri en $25n$ fyrirspurnum.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T \le 1000$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik þarftu fyrst að lesa heiltölu $n$ ($3 \le n \le 10^4$).

Samskiptareglur

Næst hefjast samskiptin. Þú getur gert í mesta lagi $25n$ fyrirspurnir í hverju prófunartilviki. Til að gera fyrirspurn þarftu að prenta eina línu ? u v ($1 \le u, v \le n$, $u \ne v$), sem lýsir fyrirspurn. Síðan þarftu að lesa niðurstöðuna úr staðalinntaki.

Til að gefa upp svarið þitt þarftu að prenta ! p1 p2 ... pn. Úttakið þitt verður að uppfylla $p_1 < p_n$. Að prenta svarið telst ekki með í takmörkuninni um $25n$ fyrirspurnir. Eftir að þú prentar svarið þarftu að lesa næsta prófunartilvik strax, eða hætta keyrslu forritsins strax.

Eftir að fyrirspurn hefur verið prentuð, ekki gleyma að prenta línuskiptatákn og tæma úttaksstrauminn (flush). Til að gera þetta geturðu notað fflush(stdout) eða cout.flush() í C++, System.out.flush() í Java, flush(output) í Pascal og stdout.flush() í Python.

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^4$.

Í þessu dæmi er tryggt að samskiptaforritið sé ekki aðlögunarhæft (non-adaptive). Það er að segja, umraðanirnar eru ákvarðaðar af handahófi eins og lýst er í dæminu áður en samskiptaferlið hefst. Þær breytast ekki eftir fyrirspurnum þínum. Alls eru $30$ prófunartilvik (þar á meðal sýnidæmið).

Dæmi

Inntak 1

2
3
2
1
1
4
1
1
1
0
2

Úttak 1

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

Athugasemd

Mynd 1: Little Cyan Fish & <?> á <?> tekin 4. mars 2026