Árið 2077 verður einfalt að semja dæmi. Vélmenni búa til dæmi með því að skilgreina nokkrar slembnar aðgerðir og leysa það svo. Dæmasmiður þarf aðeins að athuga hvort dæmið sé rétt eða ekki.

Hér er dæmi frá árinu 2077:

Gefin er umröðun $p_1, p_2, \dots, p_n$ og tryggt er að $n$ sé slétt tala. Þú vilt raða umröðuninni með því að nota aðeins eina tegund aðgerðar:

• FakeSort(l,r): Þú verður að tryggja að $r - l + 1$ sé slétt tala. Látum $k = r - l + 1$, þá verður stærstu $k/2$ stökunum og minnstu $k/2$ stökunum í samfelldu hlutrununni $p_l, p_{l+1}, \dots, p_r$ raðað óháð hvoru öðru. Það er, látum $L_1, L_2, \dots, L_{k/2}$ vera vísa stærstu $k/2$ talnanna og $S_1, S_2, \dots, S_{k/2}$ vera vísa minnstu $k/2$ talnanna. Við röðum fyrst tölunum í vísunum $L_1 \sim L_{k/2}$ og röðum síðan tölunum í vísunum $S_1 \sim S_{k/2}$.

Hér er áþreifanlegt dæmi; gerum ráð fyrir að umröðunin sé $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. Ef við köllum á FakeSort(2,7):

• $k = r - l + 1 = 6$. Samfellda hlutrunan $p_l, p_{l+1}, \dots, p_r$ er $\{5, 7, 1, 8, 6, 4\}$; við munum raða stærstu $3$ tölunum og minnstu $3$ tölunum í þessari runu óháð hvorri annarri.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; stærstu $3$ tölurnar eru feitletraðar. Eftir röðun verða þær $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; minnstu $3$ tölurnar eru feitletraðar. Eftir röðun verða þær $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

Þannig verður $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ eftir FakeSort(2,7) að $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

Vinsamlegast notaðu ekki fleiri en $114$ aðgerðir til að raða umröðuninni eða ákvarðaðu að það sé ómögulegt. Sanna má að ef hægt er að raða umröðun með þessari aðgerð, þá er til leið sem notar ekki fleiri en $114$ aðgerðir.

Inntak

Inntakið inniheldur mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 10^3$), fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan slétta heiltölu $n$ ($4 \le n \le 10^5$), lengd umröðunarinnar.

Önnur línan inniheldur $n$ heiltölur $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), umröðunina sem þú þarft að raða. Tryggt er að $p$ sé umröðun.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik, ef ómögulegt er að raða umröðuninni, prentaðu $-1$.

Annars skaltu prenta heiltölu $k$ ($0 \le k \le 114$), sem táknar fjölda aðgerða sem notaðar voru.

Í næstu $k$ línum skaltu prenta $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ er slétt tala) í hverri línu, sem táknar framkvæmd FakeSort(l,r).

Dæmi

Dæmi um inntak 1

3
4
2 1 4 3
6
3 6 5 1 2 4
8
3 2 1 7 5 4 6 8

Dæmi um úttak 1

1
1 4
-1
2
4 7
1 6