Ceci est un problème interactif !

Il existe un tableau caché $a_1, a_2, \dots, a_N$ de $N$ entiers strictement positifs distincts (où $N$ est impair) ; une copie incorrecte de ce tableau est stockée dans un autre tableau caché $b$. Chaque élément du tableau $b$ est défini comme suit :

• $b_1 = a_2$
• $b_N = a_{N-1}$
• $b_i = a_{i-1}$ ou $b_i = a_{i+1}$ pour chaque $i$ tel que $1 < i < N$ (l'un des éléments adjacents)

Vous devez déterminer s'il existe deux indices $i$ et $j$ ($i \neq j$, $1 \le i, j \le N$) tels que $b_i = b_j$. Si de tels indices existent, renvoyez-les ; sinon, indiquez qu'aucun tel couple d'indices n'existe.

Vous pouvez interroger les éléments des tableaux $a$ et $b$ à l'aide des opérations suivantes :

• 1 i : renvoie la valeur de $a_i$ ($1 \le a_i \le 10^9$)
• 2 i : renvoie la valeur de $b_i$ ($1 \le b_i \le 10^9$)

Vous pouvez poser au maximum 20 requêtes.

Protocole d'interaction

Tout d'abord, vous devez lire une ligne contenant un seul entier $T$ ($1 \le T \le 100$) désignant le nombre de cas de test.

Suit ensuite l'interaction pour $T$ cas de test.

Pour chaque cas de test, vous devez d'abord lire une ligne contenant un entier $N$ ($3 \le N \le 2\,001$, $N$ est impair).

Ensuite, l'interaction commence. Vous pouvez afficher une ligne contenant :

• 1 x (Demander $a_x$) : Puis, lisez une ligne composée d'un entier, $a_x$.
• 2 x (Demander $b_x$) : Puis, lisez une ligne composée d'un entier, $b_x$.
• 3 i j (La réponse : deux indices $i, j$ tels que $b_i = b_j$, ou -1 -1 s'il n'existe pas de tels indices) : Passez ensuite au test suivant s'il y en a un ; sinon, terminez.

Après avoir affiché chaque ligne, n'oubliez pas de vider le tampon de sortie (flush). Par exemple :

• fflush(stdout) en C/C++ ;
• System.out.flush() en Java ;
• sys.stdout.flush() en Python ;
• flush(output) en Pascal ;
• Consultez la documentation pour les autres langages.

Exemple

Entrée 1

1
7
2
2

Sortie 1

2 3
2 1
3 1 3