هذه مسألة تفاعلية!

توجد مصفوفة مخفية $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