Dies ist ein interaktives Problem!

Es gibt ein verstecktes Array $a_1, a_2, \dots, a_N$ aus $N$ paarweise verschiedenen positiven ganzen Zahlen (wobei $N$ ungerade ist); eine fehlerhafte Kopie dieses Arrays ist in einem anderen versteckten Array $b$ gespeichert. Jedes Element des Arrays $b$ ist wie folgt definiert:

• $b_1 = a_2$
• $b_N = a_{N-1}$
• $b_i = a_{i-1}$ oder $b_i = a_{i+1}$ für jedes $i$ mit $1 < i < N$ (eines der benachbarten Elemente)

Sie müssen feststellen, ob es zwei Indizes $i$ und $j$ ($i \neq j$, $1 \le i, j \le N$) gibt, sodass $b_i = b_j$ gilt. Wenn solche Indizes existieren, geben Sie diese zurück; andernfalls geben Sie an, dass keine solchen Indizes existieren.

Sie können die Elemente der Arrays $a$ und $b$ mit den folgenden Operationen abfragen:

• 1 i: gibt den Wert von $a_i$ zurück ($1 \le a_i \le 10^9$)
• 2 i: gibt den Wert von $b_i$ zurück ($1 \le b_i \le 10^9$)

Sie können maximal 20 Abfragen stellen.

Interaktionsprotokoll

Zuerst müssen Sie eine Zeile mit einer einzelnen ganzen Zahl $T$ ($1 \le T \le 100$) einlesen, die die Anzahl der Testfälle angibt.

Darauf folgt die Beschreibung der Interaktion für $T$ Testfälle.

Für jeden Testfall müssen Sie zuerst eine Zeile mit einer ganzen Zahl $N$ ($3 \le N \le 2\,001$, $N$ ist ungerade) einlesen.

Dann beginnt die Interaktion. Sie können eine Zeile ausgeben, die Folgendes enthält:

• 1 x (Frage nach $a_x$): Lesen Sie dann eine Zeile ein, die aus einer ganzen Zahl $a_x$ besteht.
• 2 x (Frage nach $b_x$): Lesen Sie dann eine Zeile ein, die aus einer ganzen Zahl $b_x$ besteht.
• 3 i j (Die Antwort: zwei Indizes $i, j$ mit $b_i = b_j$, oder -1 -1, falls es keine solchen zwei Indizes gibt): Fahren Sie dann mit dem nächsten Testfall fort, falls vorhanden; andernfalls beenden Sie das Programm.

Vergessen Sie nach der Ausgabe jeder Zeile nicht, den Ausgabepuffer zu leeren (flush). Zum Beispiel:

• fflush(stdout) in C/C++;
• System.out.flush() in Java;
• sys.stdout.flush() in Python;
• flush(output) in Pascal;
• Siehe die Dokumentation für andere Sprachen.

Beispiel

Eingabe 1

1
7
2
2

Ausgabe 1

2 3
2 1
3 1 3