Questo è un problema interattivo!

C'è un array nascosto $a_1, a_2, \dots, a_N$ di $N$ interi positivi distinti (dove $N$ è dispari); una copia errata di questo array è memorizzata in un altro array nascosto $b$. Ogni elemento dell'array $b$ è definito come segue:

• $b_1 = a_2$
• $b_N = a_{N-1}$
• $b_i = a_{i-1}$ oppure $b_i = a_{i+1}$ per ogni $i$ tale che $1 < i < N$ (uno degli elementi adiacenti)

Devi determinare se esistono due indici $i$ e $j$ ($i \neq j$, $1 \le i, j \le N$) tali che $b_i = b_j$. Se tali indici esistono, restituiscili; altrimenti, indica che non esistono tali indici.

Puoi interrogare gli elementi degli array $a$ e $b$ utilizzando le seguenti operazioni:

• 1 i: restituisce il valore di $a_i$ ($1 \le a_i \le 10^9$)
• 2 i: restituisce il valore di $b_i$ ($1 \le b_i \le 10^9$)

Puoi effettuare fino a un massimo di 20 query.

Protocollo di interazione

Per prima cosa, devi leggere una riga contenente un singolo intero $T$ ($1 \le T \le 100$) che indica il numero di casi di test.

Segue poi una descrizione dell'interazione per $T$ casi di test.

Per ogni caso di test, devi prima leggere una riga contenente un intero $N$ ($3 \le N \le 2\,001$, $N$ è dispari).

Quindi inizia l'interazione. Puoi stampare una riga contenente:

• 1 x (Chiedi di $a_x$): Poi, leggi una riga costituita da un intero, $a_x$.
• 2 x (Chiedi di $b_x$): Poi, leggi una riga costituita da un intero, $b_x$.
• 3 i j (La risposta: due indici $i, j$, dove $b_i = b_j$ oppure -1 -1 se non esistono due indici di questo tipo): Poi, procedi al test successivo se ce n'è uno; altrimenti, termina.

Dopo aver stampato ogni riga, non dimenticare di svuotare il buffer di output (flush). Ad esempio:

• fflush(stdout) in C/C++;
• System.out.flush() in Java;
• sys.stdout.flush() in Python;
• flush(output) in Pascal;
• Consulta la documentazione per gli altri linguaggi.

Esempio

Input 1

1
7
2
2

Output 1

2 3
2 1
3 1 3