To jest zadanie interaktywne!

Istnieje ukryta tablica $a_1, a_2, \dots, a_N$ złożona z $N$ parami różnych dodatnich liczb całkowitych (gdzie $N$ jest nieparzyste); niepoprawna kopia tej tablicy jest przechowywana w innej ukrytej tablicy $b$. Każdy element tablicy $b$ jest zdefiniowany następująco:

• $b_1 = a_2$
• $b_N = a_{N-1}$
• $b_i = a_{i-1}$ lub $b_i = a_{i+1}$ dla każdego $i$, gdzie $1 < i < N$ (jeden z sąsiednich elementów)

Musisz ustalić, czy istnieją dwa indeksy $i$ oraz $j$ ($i \neq j$, $1 \le i, j \le N$) takie, że $b_i = b_j$. Jeśli takie indeksy istnieją, zwróć je; w przeciwnym razie wskaż, że takie indeksy nie istnieją.

Możesz pytać o elementy tablic $a$ oraz $b$ za pomocą następujących operacji:

• 1 i: zwraca wartość $a_i$ ($1 \le a_i \le 10^9$)
• 2 i: zwraca wartość $b_i$ ($1 \le b_i \le 10^9$)

Możesz zadać maksymalnie 20 zapytań.

Protokół interakcji

Najpierw musisz wczytać wiersz zawierający jedną liczbę całkowitą $T$ ($1 \le T \le 100$) oznaczającą liczbę przypadków testowych.

Następnie następuje opis interakcji dla $T$ przypadków testowych.

Dla każdego przypadku testowego musisz najpierw wczytać wiersz zawierający jedną liczbę całkowitą $N$ ($3 \le N \le 2\,001$, $N$ jest nieparzyste).

Wtedy rozpoczyna się interakcja. Możesz wypisać jeden wiersz zawierający:

• 1 x (Zapytaj o $a_x$): Następnie wczytaj jeden wiersz składający się z jednej liczby całkowitej, $a_x$.
• 2 x (Zapytaj o $b_x$): Następnie wczytaj jeden wiersz składający się z jednej liczby całkowitej, $b_x$.
• 3 i j (Odpowiedź: dwa indeksy $i, j$, dla których $b_i = b_j$, lub -1 -1, jeśli nie istnieją takie dwa indeksy): Następnie przejdź do kolejnego testu, jeśli istnieje; w przeciwnym razie zakończ działanie programu.

Po wypisaniu każdego wiersza nie zapomnij opróżnić bufora wyjścia (flush). Na przykład:

• fflush(stdout) w C/C++;
• System.out.flush() w Javie;
• sys.stdout.flush() w Pythonie;
• flush(output) w Pascalu;
• Zobacz dokumentację dla innych języków.

Przykład

Wejście 1

1
7
2
2

Wyjście 1

2 3
2 1
3 1 3