นี่คือโจทย์แบบโต้ตอบ (interactive problem)

Menji หลงทางและทุกคนก็คิดถึงเขา หน้าที่ของคุณคือตามหาเขาให้พบ!

มีต้นไม้ทวิภาค (binary tree) $T$ ซึ่งประกอบด้วยจุดยอด $n$ จุด และแต่ละเส้นเชื่อมของต้นไม้ $T$ มีความยาวเท่ากับ $1$ Menji ซ่อนตัวอยู่ที่จุดยอด $X$ คุณทราบโครงสร้างของต้นไม้ แต่คุณไม่ทราบว่า $X$ คือจุดยอดใด

ในการหา $X$ คุณสามารถส่งสัญญาณได้ โดยคุณสามารถเลือกจุดยอด $u$ และเลือกความแรงของสัญญาณ $k$ จากนั้นส่งสัญญาณที่มีความแรง $k$ จากจุดยอด $u$ หากระยะทางระหว่าง $u$ กับ $X$ ไม่เกิน $k$ แล้ว Menji จะได้รับสัญญาณและส่งสัญญาณตอบกลับมา และคุณก็จะได้รับสัญญาณนั้น มิฉะนั้นคุณจะไม่ได้รับอะไรเลย

การส่งสัญญาณนั้นช้าและคุณกำลังรีบ ดังนั้นโปรดระบุตำแหน่งของ Menji โดยใช้การส่งสัญญาณไม่เกิน $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