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

VegiCat รู้จักอาเรย์ $a_1, a_2, \ldots, a_n$ ซึ่งแต่ละสมาชิกมีค่าเป็น $0$, $1$ หรือ $2$ เขาไม่ต้องการบอกค่าของมันให้คุณทราบโดยตรง แต่คุณสามารถถามคำถามเขาได้ ในแต่ละคำถาม คุณเลือกดัชนีสองตัวคือ $i$ และ $j$ แล้ว VegiCat จะบอกคุณว่า $a_i > a_j$ หรือไม่

VegiCat ขอให้คุณแสดงดัชนีเรียงตามลำดับไม่ลดลงของค่าในอาเรย์ที่สอดคล้องกัน กล่าวคือ จงหาการเรียงสับเปลี่ยน $p_1, p_2, \ldots, p_n$ ของ $1, 2, \ldots, n$ ที่ทำให้

$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_n}.$$

คุณสามารถถามคำถามได้ไม่เกิน $2n - 3$ ครั้งในแต่ละกรณีทดสอบ

ตัวตรวจแบบโต้ตอบสามารถปรับเปลี่ยนได้ (adaptive) นั่นหมายความว่าอาเรย์ไม่ได้ถูกกำหนดตายตัวไว้ล่วงหน้า ตัวตรวจรับประกันว่าจะมีอาเรย์ที่มีสมาชิกอยู่ใน $\{0, 1, 2\}$ อย่างน้อยหนึ่งอาเรย์ที่สอดคล้องกับคำตอบทั้งหมดที่ให้มาจนถึงปัจจุบันเสมอ การเรียงสับเปลี่ยนสุดท้ายของคุณจะต้องถูกต้องสำหรับทุกอาเรย์ที่สอดคล้องกับคำตอบทั้งหมด

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

บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 250$) แทนจำนวนกรณีทดสอบ รายละเอียดของแต่ละกรณีทดสอบมีดังต่อไปนี้

แต่ละกรณีทดสอบเริ่มต้นด้วยจำนวนเต็ม $n$ ($2 \le n \le 500$) แทนความยาวของอาเรย์

ผลรวมของ $n$ จากทุกกรณีทดสอบรวมกันไม่เกิน $500$

การโต้ตอบ

ในการถามคำถามแต่ละครั้ง ให้แสดงผลหนึ่งบรรทัดในรูปแบบต่อไปนี้:

? i j

โดยที่ $1 \le i, j \le n$ หลังจากแต่ละคำถาม ให้อ่านจำนวนเต็มหนึ่งตัว:

• $1$ หาก $a_i > a_j$;
• $0$ หาก $a_i \le a_j$

อนุญาตให้ถามคำถามที่ $i = j$ และคำถามซ้ำเดิมได้ โดยจะถูกนับรวมในจำนวนครั้งของการถามด้วย

เมื่อคุณระบุลำดับได้แล้ว ให้แสดงผลหนึ่งบรรทัดในรูปแบบต่อไปนี้:

! p_1 p_2 ... p_n

ดัชนีแต่ละตัวตั้งแต่ $1$ ถึง $n$ ต้องปรากฏขึ้นเพียงครั้งเดียวพอดี การแสดงคำตอบสุดท้ายไม่นับเป็นคำถาม

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

หลังจากแสดงผลแต่ละคำถามหรือคำตอบแล้ว ให้แสดงอักขระขึ้นบรรทัดใหม่และล้างบัฟเฟอร์ข้อมูลส่งออก (flush) ในการล้างบัฟเฟอร์ข้อมูลส่งออก คุณสามารถใช้:

• fflush(stdout) หรือ cout.flush() ในภาษา C/C++;
• System.out.flush() ในภาษา Java และ Kotlin;
• sys.stdout.flush() ในภาษา Python

หากคุณถามคำถามที่ไม่ถูกต้อง ถามเกินจำนวนครั้งที่จำกัด หรือแสดงคำตอบที่ผิด คุณจะได้รับผลการตรวจเป็น Wrong Answer ข้อมูลส่งออกที่ไม่เป็นไปตามรูปแบบที่กำหนดจะถูกตัดสินเป็น Wrong Answer เช่นกัน ในกรณีเหล่านี้ ตัวตรวจจะหยุดทำงานทันทีโดยไม่ส่งข้อความแจ้งข้อผิดพลาด

ตัวอย่าง

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

2
3

1

1

2

0

ข้อมูลส่งออก 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

หมายเหตุ

ในกรณีทดสอบแรก คำถาม ? 1 2 และ ? 2 3 ต่างก็คืนค่า $1$ ดังนั้น $a_1 > a_2 > a_3$ เพราะฉะนั้น $(3, 2, 1)$ จึงเป็นคำตอบที่ถูกต้อง

ในกรณีทดสอบที่สอง คำถาม ? 1 2 คืนค่า $0$ ดังนั้น $a_1 \le a_2$ เพราะฉะนั้น $(1, 2)$ จึงเป็นคำตอบที่ถูกต้อง