นี่เป็นโจทย์แบบโต้ตอบ อย่าลืมล้างบัฟเฟอร์ข้อมูลส่งออกหลังการพิมพ์ทุกครั้ง คุณสามารถใช้วิธีต่อไปนี้:

• fflush(stdout) หรือ cout.flush() ใน C/C++;
• System.out.flush() ใน Java และ Kotlin;
• sys.stdout.flush() ใน Python;
• สำหรับภาษาอื่น ให้ดูเอกสารของภาษานั้น

Little Cyan Fish มีการเรียงสับเปลี่ยนลับ $p_0,p_1,\ldots,p_n$ ที่มีความยาว $n+1$ ประกอบด้วยจำนวนเต็มตั้งแต่ $0$ ถึง $n$ เขาต้องการให้คุณทายการเรียงสับเปลี่ยนลับนี้ เพื่อให้ทำเช่นนั้นได้ Little Cyan Fish อนุญาตให้คุณถามได้ไม่เกิน $1024$ ครั้งในรูปแบบต่อไปนี้:

• ? i j: รับดัชนี $k$ ($0\le k\le n$) ที่ทำให้ $p_k=|p_i-p_j|$

แน่นอนว่าเพื่อให้คำถามถูกต้อง คุณต้องรับประกันว่า $i$ และ $j$ เป็นจำนวนเต็มสองจำนวนในช่วง $[0,n]$ ตัวอย่างเช่น ถ้า $p_0=2,p_1=0,p_2=1$ คำถาม ? 0 2 จะให้ดัชนี $2$ เพราะ $|p_0-p_2|=|2-1|=1=p_2$

Little Cyan Fish ต้องการให้คุณคิดกลยุทธ์เพื่อหาการเรียงสับเปลี่ยน แน่นอนว่าเขาไม่ต้องการให้คุณชนะเกมง่ายเกินไป ดังนั้นเขาจะปรับเปลี่ยนการเรียงสับเปลี่ยน $p$ ตามสถานการณ์เพื่อหลอกคุณ (ดูรายละเอียดใน “การโต้ตอบ”)

ข้อมูลนำเข้า

มีกรณีทดสอบหลายกรณี บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มหนึ่งจำนวน $T$ ($1\le T\le100$) ซึ่งระบุจำนวนกรณีทดสอบ

สำหรับแต่ละกรณีทดสอบ บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มหนึ่งจำนวน $n$ ($1\le n\le1000$) จากนั้นจึงเริ่มการโต้ตอบ

การโต้ตอบ

เพื่อถามคำถาม ให้พิมพ์หนึ่งบรรทัดในรูปแบบต่อไปนี้:

$$?\ i\ j$$

โดยที่ $i$ และ $j$ เป็นจำนวนเต็มตั้งแต่ $0$ ถึง $n$ คุณต้องรับประกันว่าจำนวนคำถามไม่เกิน $1024$ คุณจะได้รับคำตอบเป็นจำนวนเต็ม $k$ ที่ทำให้ $p_k=|p_i-p_j|$

เพื่อรายงานคำตอบ ให้พิมพ์หนึ่งบรรทัดในรูปแบบต่อไปนี้:

$$!\ p_0\ p_1\ \ldots\ p_n$$

โดยที่ $p$ คือการเรียงสับเปลี่ยนที่คุณต้องการรายงาน

หลังจากพิมพ์คำถามหรือรายงานคำตอบ อย่าลืมพิมพ์อักขระขึ้นบรรทัดใหม่และล้างสตรีมข้อมูลส่งออก

ในโจทย์นี้ โปรแกรมโต้ตอบจะปรับตัวตามสถานการณ์ นั่นหมายความว่าการเรียงสับเปลี่ยน $p$ อาจเปลี่ยนตามคำถามของคุณได้ ตราบใดที่ไม่ขัดแย้งกับคำถามก่อนหน้านี้

ตัวอย่าง

ตัวอย่างการโต้ตอบ 1

อ่าน:

1
3

เขียน:

? 2 2

อ่าน:

1

เขียน:

? 0 3

อ่าน:

3

เขียน:

! 2 0 3 1

เครื่องมือทดสอบ: มีเครื่องมือให้เพื่อช่วยผู้แข่งขันพัฒนาและทดสอบวิธีแก้ปัญหา คุณดาวน์โหลดเครื่องมือนี้ได้จากไฟล์แนบ การเรียกใช้เครื่องมือพร้อมตัวเลือก -h ควรแสดงวิธีใช้งาน เครื่องมือจะรองรับเพียงบางสถานการณ์ทดสอบและเพียงบางความสามารถของโปรแกรมตัดสินจริง