Це інтерактивна задача!

Існує прихований масив $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