Бұл — интерактивті есеп.

Менджи адасып кетті, бәрі оны сағынып жүр. Сіздің міндетіңіз — оны табу!

$n$ төбеден тұратын $T$ екілік ағашы бар, және $T$ ағашының әрбір қырының ұзындығы $1$-ге тең. Менджи $X$ төбесінде тығылып отыр. Сіз ағаштың құрылымын білесіз, бірақ $X$-ті білмейсіз.

$X$-ті табу үшін сигналдар жібере аласыз. Сіз $u$ төбесін және $k$ сигнал күшін таңдап, $u$ төбесінен күші $k$ болатын сигнал жібере аласыз. Егер $u$ мен $X$ арасындағы қашықтық $k$-дан аспаса, Менджи сигналды қабылдап, кері сигнал жібереді, ал сіз ол сигналды аласыз. Кері жағдайда сіз ештеңе алмайсыз.

Сигнал жіберу баяу жүреді, ал сіз асығыссыз, сондықтан Менджидің орнын $40$ сигналдан аспайтын сұраным арқылы анықтаңыз.

Әрекеттесу хаттамасы

Кіріс бірнеше тест жағдайларынан тұрады. Кірістің бірінші жолында тест жағдайларының санын білдіретін $T$ ($1 \le T \le 100$) бүтін саны берілген.

Әрбір тест жағдайы үшін бірінші жолда ағаштағы төбелер санын білдіретін $n$ ($2 \le n \le 3 \times 10^4$) бүтін саны берілген.

Екінші жолда $n - 1$ бүтін сан $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$) берілген, мұндағы $fa_i$ — ағаштағы $i$ төбесінің ата-анасы. Ағаштың түбірі $1$-ші төбеде орналасқан.

Ағаштың екілік ағаш екеніне кепілдік беріледі, яғни $fa_i = fa_j = fa_k$ болатындай $1 < i < j < k \le n$ индекстері табылмайды.

Сигнал жіберу үшін келесі форматта бір жол шығарыңыз:

• ? u k: $u$ төбесінде күші $k$ болатын сигнал жасайтыныңызды білдіреді. $1 \le u \le n, 0 \le k \le n$ шарттарының орындалуын қамтамасыз етуіңіз керек. Содан кейін $o$ ($o \in \{0, 1\}$) бүтін санын оқуыңыз қажет. Егер сіз сигналды алсаңыз, яғни баламалы түрде $dis(u, X) \le k$ болса, онда $o = 1$, әйтпесе $o = 0$.

Жауапты хабарлау үшін келесі форматта бір жол шығарыңыз:

• ! u: $X = u$ екенін тапқаныңызды білдіреді. Осыны шығарғаннан кейін келесі тест жағдайына көшуіңіз керек, ал егер басқа тест жағдайы қалмаса, программаны аяқтауыңыз керек.

Әрбір тест жағдайы үшін ең көп дегенде $40$ сигнал жібере аласыз. Жауапты хабарлау сигнал жіберу болып есептелмейді.

Егер сіз $40$-тан астам сигнал жіберсеңіз, немесе жіберген сигналыңыздың форматы қате болса, немесе хабарлаған жауабыңыз қате болса, әрекеттесу аяқталады да, сіз Wrong answer вердиктін аласыз.

Интерактордың бейімделгіш (adaptive) екенін ескеріңіз, яғни жауап шектеулерге және алдыңғы сұранымдардың жауаптарына қайшы келмейтіндей болып, сіздің сұранымдарыңызға байланысты өзгеруі мүмкін.

Барлық тест жағдайлары бойынша $n$ мәндерінің қосындысы $3 \times 10^4$ шамасынан аспайтынына кепілдік беріледі.

Әрбір жолды шығарғаннан кейін жол соңы таңбасын шығарып, шығыс буферін тазартуды (flush) ұмытпаңыз. Ағынды тазарту үшін C++ тілінде fflush(stdout) немесе cout.flush(), Java тілінде System.out.flush(), ал Python тілінде stdout.flush() қолдана аласыз.

Мысал

Мысал кіріс 1

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

Мысал шығыс 1

? 2 1

? 3 2

? 4 0

! 5

? 2 1

? 3 0

! 3