זוהי בעיה אינטראקטיבית!

ישנו מערך נסתר $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