Dette er et interaktivt problem!

Det finnes en skjult tabell $a_1, a_2, \dots, a_N$ med $N$ forskjellige positive heltall (der $N$ er et oddetall); en feilaktig kopi av denne tabellen er lagret i en annen skjult tabell $b$. Hvert element i tabellen $b$ er definert som følger:

• $b_1 = a_2$
• $b_N = a_{N-1}$
• $b_i = a_{i-1}$ eller $b_i = a_{i+1}$ for hver $i$ der $1 < i < N$ (et av naboelementene)

Du må avgjøre om det finnes to indekser $i$ og $j$ ($i \neq j$, $1 \le i, j \le N$) slik at $b_i = b_j$. Hvis slike indekser finnes, returner dem; ellers, angi at ingen slike indekser finnes.

Du kan spørre om elementene i tabellene $a$ og $b$ ved å bruke følgende operasjoner:

• 1 i: returnerer verdien av $a_i$ ($1 \le a_i \le 10^9$)
• 2 i: returnerer verdien av $b_i$ ($1 \le b_i \le 10^9$)

Du kan stille opptil maksimalt 20 spørringer.

Interaksjonsprotokoll

Først må du lese en linje som inneholder et enkelt heltall $T$ ($1 \le T \le 100$) som angir antallet testtilfeller.

Deretter følger en beskrivelse av interaksjonen for $T$ testtilfeller.

For hvert testtilfelle må du først lese en linje som inneholder ett heltall $N$ ($3 \le N \le 2\,001$, $N$ er et oddetall).

Deretter starter interaksjonen. Du kan skrive ut én linje som inneholder:

• 1 x (Spør om $a_x$): Les deretter én linje som består av ett heltall, $a_x$.
• 2 x (Spør om $b_x$): Les deretter én linje som består av ett heltall, $b_x$.
• 3 i j (Svaret: to indekser $i, j$, der $b_i = b_j$ eller -1 -1 hvis det ikke finnes to slike indekser): Gå deretter videre til neste test hvis det er noen; ellers, avslutt.

Etter å ha skrevet ut hver linje, ikke glem å tømme utdatabufferen (flush). For eksempel:

• fflush(stdout) i C/C++;
• System.out.flush() i Java;
• sys.stdout.flush() i Python;
• flush(output) i Pascal;
• Se dokumentasjonen for andre språk.

Eksempel

Inndata 1

1
7
2
2

Utdata 1

2 3
2 1
3 1 3