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

— "โหยหาแดนไกล" · การแข่งขันเขียนโปรแกรมระดับอุดมศึกษาแห่งประเทศจีน ครั้งที่ 10 รอบชิงชนะเลิศ

นี่คือโจทย์ปัญหาแบบโต้ตอบ (interactive problem)

เอาล่ะ บางทีคุณอาจจะลองดูได้ว่ามันจะยากสักแค่ไหน Little Cyan Fish รู้สึกว่าชีวิตของเขาคือการเรียงสับเปลี่ยนที่ไม่ทราบรูปร่าง ผู้คนมักพูดเสมอว่าโลกนี้เต็มไปด้วยความสุ่ม แต่ทำไม Little Cyan Fish ถึงได้โชคร้ายอยู่ตลอดเลยล่ะ...? อ๋อ! บางทีความสุ่มอาจจะลึกซึ้งแบบนี้ก็ได้! ดังนั้น Little Cyan Fish จึงตัดสินใจว่าการเรียงสับเปลี่ยนของเขาอันนี้จะถูกสร้างขึ้นแบบสุ่มด้วยวิธีต่อไปนี้:

• สร้างการเรียงสับเปลี่ยนแบบสุ่ม $p_1, p_2, \dots, p_n$: โดยสุ่มเลือกอย่างสม่ำเสมอจากการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมด $n!$ แบบของ $1$ ถึง $n$
• ถ้า $p_1 > p_n$ ให้กลับด้านการเรียงสับเปลี่ยนทั้งหมด

คุณไม่สามารถสังเกตโครงสร้างของการเรียงสับเปลี่ยนได้โดยตรง แต่ Little Cyan Fish ได้มอบพลังวิเศษให้คุณ นั่นคือการถาม! ในแต่ละครั้ง คุณสามารถสอบถามแบบโต้ตอบเพื่อหาค่าระยะห่างระหว่างตัวเลขสองตัวในการเรียงสับเปลี่ยนในระบบมอดูโล $3$ ได้ กล่าวอย่างเจาะจงคือ ในแต่ละครั้งคุณสามารถเลือกตัวเลขสองตัว $u, v$ ($1 \le u, v \le n$, $u \ne v$) การเรียงสับเปลี่ยนจะบอกค่าระยะห่างระหว่างตัวเลขสองตัวนี้ในระบบมอดูโล $3$ ให้คุณทราบ (กล่าวคือ หาดัชนีสองตัว $i, j$ ที่สอดคล้องกับ $p_i = u, p_j = v$ แล้วการเรียงสับเปลี่ยนจะตอบค่า $|i - j| \bmod 3$)

ตอนนี้ Little Cyan Fish ต้องการให้คุณลองดูว่าคุณจะได้อะไรบ้าง คุณต้องช่วย Little Cyan Fish ระบุการเรียงสับเปลี่ยนนี้โดยใช้การถามไม่เกิน $25n$ ครั้ง

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

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

สำหรับแต่ละชุดทดสอบ ก่อนอื่นคุณต้องอ่านจำนวนเต็ม $n$ ($3 \le n \le 10^4$)

โปรโตคอลการโต้ตอบ

ถัดไป การโต้ตอบจะเริ่มต้นขึ้น คุณสามารถทำการถามได้ไม่เกิน $25n$ ครั้งในแต่ละชุดทดสอบ ในการถามหนึ่งครั้ง คุณต้องแสดงผลหนึ่งบรรทัดคือ ? u v ($1 \le u, v \le n$, $u \ne v$) เพื่ออธิบายคำถาม จากนั้นคุณต้องอ่านผลลัพธ์จากข้อมูลนำเข้ามาตรฐาน

ในการส่งคำตอบของคุณ คุณต้องแสดงผล ! p1 p2 ... pn ผลลัพธ์ของคุณจะต้องสอดคล้องกับเงื่อนไข $p_1 < p_n$ การแสดงผลคำตอบจะไม่ถูกนับรวมในขีดจำกัดการถาม $25n$ ครั้ง หลังจากที่คุณแสดงผลคำตอบแล้ว คุณต้องอ่านชุดทดสอบถัดไปทันที หรือจบการทำงานของโปรแกรมทันที

หลังจากแสดงผลคำถามแล้ว อย่าลืมแสดงผลอักขระขึ้นบรรทัดใหม่และทำการ flush สตรีมข้อมูลส่งออก ในการทำเช่นนี้ คุณสามารถใช้ fflush(stdout) หรือ cout.flush() ในภาษา C++, System.out.flush() ในภาษา Java, flush(output) ในภาษา Pascal และ stdout.flush() ในภาษา Python

รับประกันว่าผลรวมของ $n$ ในทุกชุดทดสอบจะไม่เกิน $10^4$

ในปัญหานี้ รับประกันว่าโปรแกรมตรวจแบบโต้ตอบเป็นแบบไม่ปรับตัว (non-adaptive) นั่นคือ การเรียงสับเปลี่ยนจะถูกกำหนดไว้แบบสุ่มตามที่โจทย์ระบุก่อนเริ่มกระบวนการโต้ตอบ และจะไม่เปลี่ยนแปลงตามคำถามของคุณ มีชุดทดสอบทั้งหมด $30$ ชุด (รวมชุดทดสอบตัวอย่างด้วย)

ตัวอย่าง

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

2
3
2
1
1
4
1
1
1
0
2

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

? 1 2
? 2 3
? 1 3
! 1 3 2
? 2 3
? 3 1
? 1 4
? 2 4
? 2 1
! 2 3 1 4

หมายเหตุ

รูปที่ 1: Little Cyan Fish กับ <?> ที่ <?> ถ่ายเมื่อวันที่ 4 มีนาคม 2026