นี่คือโจทย์แบบโต้ตอบ (Interactive Problem)!

มีอาร์เรย์ซ่อนอยู่ $a_1, a_2, \dots, a_N$ ซึ่งประกอบด้วยจำนวนเต็มบวกที่แตกต่างกันทั้งหมด $N$ ตัว (โดยที่ $N$ เป็นจำนวนคี่); สำเนาที่ผิดพลาดของอาร์เรย์นี้ถูกเก็บไว้ในอาร์เรย์ที่ซ่อนอยู่อีกอันคือ $b$ แต่ละสมาชิกของอาร์เรย์ $b$ ถูกนิยามดังนี้:

• $b_1 = a_2$
• $b_N = a_{N-1}$
• $b_i = a_{i-1}$ หรือ $b_i = a_{i+1}$ สำหรับแต่ละ $i$ ที่ $1 < i < N$ (หนึ่งในสมาชิกที่อยู่ติดกัน)

คุณต้องพิจารณาว่ามีดัชนี $i$ และ $j$ สองตัว ($i \neq j$, $1 \le i, j \le N$) ที่ทำให้ $b_i = b_j$ หรือไม่ หากมีดัชนีดังกล่าว ให้คืนค่าดัชนีเหล่านั้น มิฉะนั้น ให้ระบุว่าไม่มีดัชนีดังกล่าว

คุณสามารถสอบถามสมาชิกของอาร์เรย์ $a$ และ $b$ โดยใช้การดำเนินการต่อไปนี้:

• 1 i: คืนค่าของ $a_i$ ($1 \le a_i \le 10^9$)
• 2 i: คืนค่าของ $b_i$ ($1 \le b_i \le 10^9$)

คุณสามารถถามคำถามได้สูงสุดไม่เกิน 20 ครั้ง

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

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

จากนั้นจะเป็นการโต้ตอบสำหรับ $T$ กรณีทดสอบ

สำหรับแต่ละกรณีทดสอบ คุณต้องอ่านบรรทัดที่มีจำนวนเต็มหนึ่งตัวคือ $N$ ($3 \le N \le 2\,001$, $N$ เป็นจำนวนคี่) ก่อน

จากนั้นการโต้ตอบจะเริ่มต้นขึ้น คุณสามารถพิมพ์หนึ่งบรรทัดที่ประกอบด้วย:

• 1 x (ถามเกี่ยวกับ $a_x$): จากนั้น อ่านหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็มหนึ่งตัวคือ $a_x$
• 2 x (ถามเกี่ยวกับ $b_x$): จากนั้น อ่านหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็มหนึ่งตัวคือ $b_x$
• 3 i j (คำตอบ: ดัชนีสองตัว $i, j$ ที่ $b_i = b_j$ หรือ -1 -1 หากไม่มีดัชนีสองตัวดังกล่าว): จากนั้น ดำเนินการต่อในกรณีทดสอบถัดไปหากมี มิฉะนั้น ให้จบการทำงาน

หลังจากแสดงผลแต่ละบรรทัด อย่าลืมล้างบัฟเฟอร์เอาต์พุต (flush) ตัวอย่างเช่น:

• fflush(stdout) ใน C/C++;
• System.out.flush() ใน Java;
• sys.stdout.flush() ใน Python;
• flush(output) ใน Pascal;
• ดูเอกสารประกอบสำหรับภาษาอื่นๆ

ตัวอย่าง

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

1
7
2
2

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

2 3
2 1
3 1 3