Þetta er gagnvirkt verkefni.

Menji er týndur og allir sakna hans. Það er þitt hlutverk að finna hann!

Til er tvíundartré $T$ sem samanstendur af $n$ hnútum, og hver leggur trésins $T$ hefur lengdina $1$. Menji felur sig í hnúti $X$. Þú þekkir byggingu trésins, en þú veist ekki hver $X$ er.

Til að finna $X$ getur þú sent merki. Þú getur valið hnút $u$ og merkisstyrk $k$, og síðan sent merki af styrk $k$ frá hnúti $u$. Ef fjarlægðin milli $u$ og $X$ er ekki meiri en $k$ mun Menji nema merkið og senda merki til baka, og þú munt nema það merki. Annars nemur þú ekki neitt.

Það er hægfara að senda merki og þér liggur á, svo vinsamlegast ákvarðaðu staðsetningu Menji í ekkifleiri en $40$ merkjum.

Samskiptareglur

Inntakið inniheldur mörg prófunartilvik. Fyrsta lína inntaksins inniheldur heiltölu $T$ ($1 \le T \le 100$), fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan heiltölu $n$ ($2 \le n \le 3 \times 10^4$), fjölda hnúta í trénu.

Önnur línan inniheldur $n - 1$ heiltölur $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$), þar sem $fa_i$ er foreldri $i$ í trénu. Rót trésins er í hnúti $1$.

Tryggt er að tréð sé tvíundartré, þ.e. ekki eru til $1 < i < j < k \le n$ þannig að $fa_i = fa_j = fa_k$.

Til að senda merki skal prenta eina línu á eftirfarandi sniði:

• ? u k: Gefur til kynna að þú búir til merki í hnúti $u$ með styrk $k$. Þú þarft að tryggja að $1 \le u \le n, 0 \le k \le n$. Síðan þarftu að lesa heiltölu $o$ ($o \in \{0, 1\}$). Ef þú namst merkið, eða jafngilt því að $dis(u, X) \le k$, þá er $o = 1$, annars er $o = 0$.

Til að tilkynna svarið skal prenta eina línu á eftirfarandi sniði:

• ! u: Gefur til kynna að þú hafir fundið $X = u$. Þú þarft að halda áfram í næsta prófunartilvik eftir að hafa prentað þetta, eða hætta keyrslu ef engin fleiri eru eftir.

Fyrir hvert prófunartilvik getur þú sent í mesta lagi $40$ merki. Að tilkynna svarið telst ekki sem sending merkis.

Ef þú sendir fleiri en $40$ merki, eða merkið sem þú sendir er á röngu sniði, eða svarið sem þú tilkynntir er rangt, þá lýkur samskiptunum og þú færð niðurstöðuna Wrong answer.

Athugið að samskiptaforritið er aðlögunarhæft (adaptive), sem þýðir að svarið getur breyst eftir fyrirspurnum þínum svo lengi sem það helst í samræmi við skorðurnar og svörin við fyrri fyrirspurnum.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $3 \times 10^4$.

Eftir að hver lína er prentuð má ekki gleyma að prenta línuskil og tæma úttaksbiðminnið (flush). Þú getur notað fflush(stdout) eða cout.flush() í C++, System.out.flush() í Java og stdout.flush() í Python.

Dæmi

Sýnidæmi inntaks 1

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

Sýnidæmi úttaks 1

? 2 1

? 3 2

? 4 0

! 5

? 2 1

? 3 0

! 3