זוהי בעיה אינטראקטיבית.

מנג'י הלך לאיבוד וכולם מתגעגעים אליו. התפקיד שלכם הוא למצוא אותו!

ישנו עץ בינארי $T$, המורכב מ-$n$ קודקודים, ואורך כל קשת בעץ $T$ הוא $1$. מנג'י מסתתר בקודקוד $X$. אתם יודעים את מבנה העץ, אך אינכם יודעים מהו $X$.

כדי למצוא את $X$, באפשרותכם לשלוח אותות. תוכלו לבחור קודקוד $u$ ולבחור עוצמת אות $k$, ואז לשלוח אות בעוצמה $k$ מקודקוד $u$. אם המרחק בין $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$.

מובטח כי העץ הוא עץ בינארי, כלומר לא קיימים $1 < i < j < k \le n$ כך ש-$fa_i = fa_j = fa_k$.

כדי לשלוח אות, הדפיסו שורה יחידה בפורמט הבא:

• ? 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). תוכלו להשתמש ב-fflush(stdout) או ב-cout.flush() עבור C++, ב-System.out.flush() עבור Java, וב-stdout.flush() עבור Python.

דוגמה

קלט לדוגמה 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