Ini adalah soal interaktif!

Terdapat sebuah larik tersembunyi $a_1, a_2, \dots, a_N$ yang terdiri dari $N$ bilangan bulat positif berbeda (dengan $N$ ganjil); salinan yang salah dari larik ini disimpan di larik tersembunyi lainnya $b$. Setiap elemen dari larik $b$ didefinisikan sebagai berikut:

• $b_1 = a_2$
• $b_N = a_{N-1}$
• $b_i = a_{i-1}$ atau $b_i = a_{i+1}$ untuk setiap $i$ dengan $1 < i < N$ (salah satu dari elemen yang bersebelahan)

Anda perlu menentukan apakah terdapat dua indeks $i$ dan $j$ ($i \neq j$, $1 \le i, j \le N$) sehingga $b_i = b_j$. Jika indeks tersebut ada, kembalikan keduanya; jika tidak, nyatakan bahwa tidak ada indeks seperti itu.

Anda dapat melakukan kueri terhadap elemen-elemen larik $a$ dan $b$ menggunakan operasi berikut:

• 1 i: mengembalikan nilai $a_i$ ($1 \le a_i \le 10^9$)
• 2 i: mengembalikan nilai $b_i$ ($1 \le b_i \le 10^9$)

Anda dapat mengajukan maksimal hingga 20 kueri.

Protokol Interaksi

Pertama, Anda harus membaca satu baris yang berisi satu bilangan bulat $T$ ($1 \le T \le 100$) yang menyatakan banyaknya kasus uji.

Kemudian diikuti interaksi untuk $T$ kasus uji.

Untuk setiap kasus uji, Anda harus terlebih dahulu membaca satu baris yang berisi satu bilangan bulat $N$ ($3 \le N \le 2\,001$, $N$ ganjil).

Kemudian interaksi dimulai. Anda dapat mencetak satu baris yang berisi:

• 1 x (Bertanya tentang $a_x$): Kemudian, baca satu baris yang terdiri dari satu bilangan bulat, $a_x$.
• 2 x (Bertanya tentang $b_x$): Kemudian, baca satu baris yang terdiri dari satu bilangan bulat, $b_x$.
• 3 i j (Jawaban: dua indeks $i, j$, dengan $b_i = b_j$ atau -1 -1 jika tidak ada dua indeks tersebut): Kemudian, lanjutkan ke kasus uji berikutnya jika ada; jika tidak, hentikan program.

Setelah mencetak setiap baris, jangan lupa untuk melakukan flush pada keluaran. Sebagai contoh:

• fflush(stdout) di C/C++;
• System.out.flush() di Java;
• sys.stdout.flush() di Python;
• flush(output) di Pascal;
• Lihat dokumentasi untuk bahasa lainnya.

Contoh

Masukan 1

1
7
2
2

Keluaran 1

2 3
2 1
3 1 3