Background

A well-known Luogu internet celebrity, comrade €€£, leader of the €€£ official team, passed away on April 17 after unsuccessful emergency treatment in the hospital.

€€£ was a well-known person on Luogu. He joined Luogu in 2021 and founded the €€£ official team in the same year. During his time in charge, he worked diligently, made jokes seriously, worked hard on creating problems, and contributed to making the “joke revolution” more standardized, modernized, and formalized.

Regarding the retirement of €€£, Uvocde felt deeply sad. At this time, he remembered €€£ ’s deep love for construction problems, so he made this problem to commemorate €€£.

Problem Description

There are $T$ queries. Each query gives a sequence $a$ of length $n$, and it is guaranteed that $a$ is a permutation of $1\sim n$.

You may choose a number $x$. Then, each time you may move a subsegment of length $x+1$ or a subsegment of length $x-1$ forward or backward by $x$ positions within the original sequence, and move the part passed over into the vacated space.

Please sort $a$ in nondecreasing order within $80\times n$ operations.

Input Format

The first line contains a positive integer $T$.

Then there are $2 \times T$ lines. Every two lines represent one query.

For each query, the format is: first a line with a positive integer $n$, then a line with $n$ positive integers representing $a_1,\ldots,a_n$.

Output Format

Output a total of $T$ groups.

If a query has no solution, output only $-1$.

If it has a solution, output $m+2$ lines in total:

The first two lines each contain one number, respectively $x,m$, where $m$ is the number of operations, and $x$ is as described above.

Then output $m$ lines, each with three numbers. The first number indicates the direction ($0$ means left, $1$ means right). The next two numbers $l,r$ represent the left and right endpoints of the shifted segment.

Your solution must satisfy:

• $2\leq x\leq n$, $0\leq m\leq 80n$.
• For each operation:
  • $1\leq l\leq r\leq n$.
  • $r-l+1=x-1$ or $r-l+1=x+1$.
  • When shifting right, $r\leq n-x$; when shifting left, $l\geq x+1$.

This problem uses $\text{SPJ}$. You will get points as long as your operations are correct or you correctly determine that there is no solution.

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

3
4
1 1 4
1 2 3
1 1 2
0 5 6
-1

Hint

[Sample Explanation]

For the sample $2\ 1\ 4\ 7\ 6\ 5\ 3$:

Let $x$ be $3$, and perform $4$ operations in total:

0. 2 1 4 7 6 5 3, shift right.
1. 6 5 3 2 1 4 7, shift right.
2. 6 2 1 4 5 3 7, shift right.
3. 1 4 5 6 2 3 7, shift left.
4. 1 2 3 4 5 6 7, sorting finished.

[Constraints]

For $100\%$ of the testdata, $1\le T\le10^4,\ 2\le n\le 10^4,\ \sum n\le10^4$. It is guaranteed that the permutation is uniformly random among all permutations.

Translated by ChatGPT 5