¡Este es un problema interactivo!

Hay un arreglo oculto $a_1, a_2, \dots, a_N$ de $N$ enteros positivos distintos (donde $N$ es impar); una copia incorrecta de este arreglo está almacenada en otro arreglo oculto $b$. Cada elemento del arreglo $b$ se define como sigue:

• $b_1 = a_2$
• $b_N = a_{N-1}$
• $b_i = a_{i-1}$ o $b_i = a_{i+1}$ para cada $i$ donde $1 < i < N$ (uno de los elementos adyacentes)

Debes determinar si existen dos índices $i$ y $j$ ($i \neq j$, $1 \le i, j \le N$) tales que $b_i = b_j$. Si dichos índices existen, devuélvelos; de lo contrario, indica que no existen tales índices.

Puedes consultar los elementos de los arreglos $a$ y $b$ mediante las siguientes operaciones:

• 1 i: devuelve el valor de $a_i$ ($1 \le a_i \le 10^9$)
• 2 i: devuelve el valor de $b_i$ ($1 \le b_i \le 10^9$)

Puedes hacer un máximo de 20 consultas.

Protocolo de interacción

Primero, debes leer una línea que contiene un solo entero $T$ ($1 \le T \le 100$) que denota el número de casos de prueba.

Luego sigue la interacción para $T$ casos de prueba.

Para cada caso de prueba, primero debes leer una línea que contiene un entero $N$ ($3 \le N \le 2\,001$, $N$ es impar).

Luego comienza la interacción. Puedes imprimir una línea que contenga:

• 1 x (Preguntar por $a_x$): Luego, lee una línea que consta de un entero, $a_x$.
• 2 x (Preguntar por $b_x$): Luego, lee una línea que consta de un entero, $b_x$.
• 3 i j (La respuesta: dos índices $i, j$, donde $b_i = b_j$, o -1 -1 si no existen tales dos índices): Luego, procede al siguiente caso de prueba si hay alguno; de lo contrario, termina.

Después de imprimir cada línea, no olvides vaciar el búfer de salida (flush). Por ejemplo:

• fflush(stdout) en C/C++;
• System.out.flush() en Java;
• sys.stdout.flush() en Python;
• flush(output) en Pascal;
• Consulta la documentación para otros lenguajes.

Ejemplo

Entrada 1

1
7
2
2

Salida 1

2 3
2 1
3 1 3