Detta är ett interaktivt problem!

Det finns en dold array $a_1, a_2, \dots, a_N$ med $N$ olika positiva heltal (där $N$ är udda); en felaktig kopia av denna array lagras i en annan dold array $b$. Varje element i arrayen $b$ definieras enligt följande:

• $b_1 = a_2$
• $b_N = a_{N-1}$
• $b_i = a_{i-1}$ eller $b_i = a_{i+1}$ för varje $i$ där $1 < i < N$ (ett av de intilliggande elementen)

Du måste avgöra om det finns två index $i$ och $j$ ($i \neq j$, $1 \le i, j \le N$) sådana att $b_i = b_j$. Om sådana index finns, returnera dem; ange annars att inga sådana index finns.

Du kan fråga efter elementen i arrayerna $a$ och $b$ med följande operationer:

• 1 i: returnerar värdet på $a_i$ ($1 \le a_i \le 10^9$)
• 2 i: returnerar värdet på $b_i$ ($1 \le b_i \le 10^9$)

Du kan ställa högst 20 frågor.

Interaktionsprotokoll

Först måste du läsa en rad som innehåller ett enda heltal $T$ ($1 \le T \le 100$) som anger antalet testfall.

Därefter följer en beskrivning av interaktionen för $T$ testfall.

För varje testfall måste du först läsa en rad som innehåller ett heltal $N$ ($3 \le N \le 2\,001$, $N$ är udda).

Sedan börjar interaktionen. Du kan skriva ut en rad som innehåller:

• 1 x (Fråga om $a_x$): Läs sedan en rad som består av ett heltal, $a_x$.
• 2 x (Fråga om $b_x$): Läs sedan en rad som består av ett heltal, $b_x$.
• 3 i j (Svaret: två index $i, j$, där $b_i = b_j$ eller -1 -1 om det inte finns några sådana två index): Gå sedan vidare till nästa test om det finns något; avsluta annars.

Glöm inte att tömma utdatabufferten (flush) efter att du har skrivit ut varje rad. Till exempel:

• fflush(stdout) i C/C++;
• System.out.flush() i Java;
• sys.stdout.flush() i Python;
• flush(output) i Pascal;
• Se dokumentationen för andra språk.

Exempel

Indata 1

1
7
2
2

Utdata 1

2 3
2 1
3 1 3