Background

As the spring rain is about to end, a swallow suddenly chirps softly, stirring up ripples on the spring water. The ripples bring back memories from last year. The memories have a fragrance, filling the eaves. Under the eaves, the old swallow nest is worn and broken. Tears cannot help but fall. Looking up at the returning swallows, something moves in the heart, as if they are familiar faces from long ago.

Problem Description

$n$ swallows fly across the sunset. In order from front to back, the size of the $i$-th swallow is $p_i$, and $p$ is a permutation of length $n$.

Now you may perform at most $L$ operations of the following type:

• Choose three integers $i, j, k$ such that $1 \le i < j < k \le n$. If $p_i > p_k$, swap the $i$-th and $j$-th swallows; otherwise, swap the $j$-th and $k$-th swallows.

To make the formation neat, we want the swallows to be in increasing order from front to back, that is, $p_i = i$ for all $1 \le i \le n$.

Determine whether the goal can be achieved. If yes, construct a sequence of operations that satisfies the requirements.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

• The first line contains two integers $n, L$.
• The second line contains $n$ integers $p_1, p_2, \ldots, p_n$.

Output Format

For each test case:

• If it is impossible to make $p$ increasing using at most $L$ operations, output one line -1.
• Otherwise, output an integer $x$ on the first line, indicating the number of operations. Then output $x$ lines, each containing three integers $i, j, k$, describing an operation. You must guarantee that $0 \le x \le L$ and $1 \le i < j < k \le n$.

1
4 4
4 2 1 3

2
1 3 4
2 3 4

Hint

[Hint]

A permutation of length $n$ is an array in which every positive integer from $1$ to $n$ appears exactly once. For example, $[3,1,2]$ is a permutation of length $3$, while $[5,5,1,2,3]$ is not a permutation.

[Explanation for Sample 1]

• In the first operation, $i = 1, j = 3, k = 4$. Since $p_1 > p_4$, we swap $p_1$ and $p_3$, and now $p = [1,2,4,3]$.
• In the second operation, $i = 2, j = 3, k = 4$. Since $p_2 < p_4$, we swap $p_3$ and $p_4$, and now $p = [1,2,3,4]$.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (5 points): $n \le 3$.
• Subtask 2 (5 points): $n \le 4$.
• Subtask 3 (5 points): $T \le 50$, $n \le 8$.
• Subtask 4 (10 points): $n \le 8$.
• Subtask 5 (25 points): $L = n + 2$.
• Subtask 6 (25 points): $L = n + 1$.
• Subtask 7 (25 points): no special restrictions.

For $100\%$ of the testdata, $1 \le T \le 10^5$, $1 \le n, \sum n \le 2 \times 10^6$, $n \le L \le n + 2$, and $p$ is a permutation of $1 \sim n$.

Translated by ChatGPT 5