Tämä on vuorovaikutteinen tehtävä.

Menji on eksynyt ja kaikki kaipaavat häntä. Sinun tehtäväsi on löytää hänet!

On binääripuu $T$, joka koostuu $n$ solmusta, ja puun $T$ jokaisen kaaren pituus on $1$. Menji piileskelee solmussa $X$. Tunnet puun rakenteen, mutta et tiedä solmua $X$.

Löytääksesi solmun $X$ voit lähettää signaaleja. Voit valita solmun $u$ ja signaalin voimakkuuden $k$ ja lähettää sitten voimakkuuden $k$ signaalin solmusta $u$. Jos solmujen $u$ ja $X$ välinen etäisyys on enintään $k$, Menji vastaanottaa signaalin ja lähettää signaalin takaisin, jolloin sinä vastaanotat sen. Muussa tapauksessa et vastaanota mitään.

Signaalien lähettäminen on hidasta ja sinulla on kiire, joten määritä Menjin sijainti enintään $40$ signaalilla.

Vuorovaikutusprotokolla

Syöte sisältää useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 100$), testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää kokonaisluvun $n$ ($2 \le n \le 3 \times 10^4$), puun solmujen lukumäärän.

Toinen rivi sisältää $n - 1$ kokonaislukua $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$), missä $fa_i$ on solmun $i$ vanhempi puussa. Puun juuri on solmu $1$.

On taattu, että puu on binääripuu, eli ei ole olemassa sellaisia $1 < i < j < k \le n$, joilla $fa_i = fa_j = fa_k$.

Lähettääksesi signaalin tulosta yksi rivi seuraavassa muodossa:

• ? u k: Ilmaisee, että luot solmussa $u$ signaalin, jonka voimakkuus on $k$. Sinun on varmistettava, että $1 \le u \le n, 0 \le k \le n$. Sen jälkeen sinun on luettava kokonaisluku $o$ ($o \in \{0, 1\}$). Jos vastaanotit signaalin, eli yhtäpitävästi $dis(u, X) \le k$, niin $o = 1$, muuten $o = 0$.

Ilmoittaaksesi vastauksen tulosta yksi rivi seuraavassa muodossa:

• ! u: Ilmaisee, että olet selvittänyt $X = u$. Tämän tulostamisen jälkeen sinun tulee siirtyä seuraavaan testitapaukseen tai lopettaa ohjelman suoritus, jos testitapauksia ei ole enempää.

Jokaisessa testitapauksessa voit lähettää enintään $40$ signaalia. Vastauksen ilmoittamista ei lasketa signaalin lähettämiseksi.

Jos lähetät enemmän kuin $40$ signaalia, lähettämäsi signaali on väärän muotoinen tai ilmoittamasi vastaus on väärin, vuorovaikutus päättyy ja saat tuomion Wrong answer.

Huomaa, että vuorovaikutusohjelma on mukautuva (adaptive), mikä tarkoittaa, että vastaus voi muuttua kyselyjesi mukaan, kunhan se pysyy ristiriidattomana rajoitteiden ja aiempiin kyselyihin annettujen vastausten kanssa.

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

Jokaisen rivin tulostamisen jälkeen älä unohda tulostaa rivinvaihtoa ja tyhjentää tulostuspuskuria (flush). Voit käyttää C++:ssa kutsua fflush(stdout) tai cout.flush(), Javassa kutsua System.out.flush() ja Pythonissa kutsua stdout.flush().

Esimerkki

Esimerkkisyöte 1

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

Esimerkkituloste 1

? 2 1

? 3 2

? 4 0

! 5

? 2 1

? 3 0

! 3