2077 жылы есеп құрастыру оңай болады. Роботтар бірнеше кездейсоқ амалдарды белгілеу арқылы есеп құрастырып, оны өздері шығарады. Есеп авторына тек есептің дұрыс не бұрыс екенін тексеру ғана қалады.

Міне, 2077 жылдан келген есеп:

$p_1, p_2, \dots, p_n$ алмастыруы берілген, мұндағы $n$ жұп сан екеніне кепілдік беріледі. Сіз бұл алмастыруды тек бір ғана амал түрін қолданып сұрыптағыңыз келеді:

• FakeSort(l,r): $r - l + 1$ жұп сан болуын қамтамасыз етуіңіз керек. $k = r - l + 1$ болсын, сонда $p_l, p_{l+1}, \dots, p_r$ үзіліссіз ішкі тізбегіндегі ең үлкен $k/2$ элемент пен ең кіші $k/2$ элемент бір-бірінен тәуелсіз сұрыпталады. Яғни, $L_1, L_2, \dots, L_{k/2}$ — ең үлкен $k/2$ санның индекстері, ал $S_1, S_2, \dots, S_{k/2}$ — ең кіші $k/2$ санның индекстері болсын. Біз алдымен $L_1 \sim L_{k/2}$ индекстеріндегі сандарды сұрыптаймыз, содан кейін $S_1 \sim S_{k/2}$ индекстеріндегі сандарды сұрыптаймыз.

Нақты мысал келтірейік: алмастыру $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ болсын делік. Егер біз FakeSort(2,7) шақырсақ:

• $k = r - l + 1 = 6$. $p_l, p_{l+1}, \dots, p_r$ үзіліссіз ішкі тізбегі $\{5, 7, 1, 8, 6, 4\}$ болады; біз осы тізбектегі ең үлкен $3$ санды және ең кіші $3$ санды бір-бірінен тәуелсіз сұрыптаймыз.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; ең үлкен $3$ сан қалың қаріппен берілген. Сұрыптағаннан кейін олар $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$ болады.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; ең кіші $3$ сан қалың қаріппен берілген. Сұрыптағаннан кейін олар $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$ болады.

Сонымен, $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ алмастыруы FakeSort(2,7) амалынан кейін $\{2, 1, 6, 4, 7, 8, 5, 3\}$ болады.

Алмастыруды сұрыптау үшін $114$ амалдан артық қолданбаңыз немесе мұның мүмкін емес екенін анықтаңыз. Егер алмастыруды осы амалмен сұрыптауға болатын болса, онда $114$ амалдан аспайтын әдіс бар екенін дәлелдеуге болады.

Кіріс деректер

Кіріс деректер бірнеше тест жиынтығынан тұрады. Кірістің бірінші жолында тест жиынтықтарының санын білдіретін бүтін сан $T$ ($1 \le T \le 10^3$) берілген.

Әрбір тест жиынтығы үшін бірінші жолда алмастырудың ұзындығын білдіретін жұп бүтін сан $n$ ($4 \le n \le 10^5$) берілген.

Екінші жолда сізге сұрыптау қажет алмастыруды білдіретін $n$ бүтін сан $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) берілген. $p$ алмастыру екеніне кепілдік беріледі.

Барлық тест жиынтықтары бойынша $n$ сандарының қосындысы $2 \times 10^5$ шамасынан аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жиынтығы үшін алмастыруды сұрыптау мүмкін болмаса, $-1$ шығарыңыз.

Әйтпесе, қолданылған амалдар санын білдіретін бүтін сан $k$ ($0 \le k \le 114$) шығарыңыз.

Келесі $k$ жолдың әрқайсысында FakeSort(l,r) орындауды білдіретін $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ жұп) сандарын шығарыңыз.

Мысалдар

1-мысал кіріс

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

1-мысал шығыс

1
1 4
-1
2
4 7
1 6