Swallows in the Sunset Sorting

There are \(n\) swallows flying in the sunset. They appear in order, and the size of the \(i\)th swallow is \(p_i\) (so that \(p = [p_1, p_2, \dots, p_n]\) is a permutation of \(\{1,2,\dots,n\}\)).

You are allowed to perform at most \(L\) operations. In each operation, you choose three indices \(i,j,k\) with \(1 \le i < j < k \le n\) and do the following:

• If \(p_i > p_k\), swap \(p_i\) and \(p_j\).
• Otherwise, swap \(p_j\) and \(p_k\).

The goal is to reorder the swallows so that they are in increasing order (i.e. \(p_i = i\) for all \(1 \le i \le n\)). Determine whether it is possible to achieve the goal. If it is possible, output a valid sequence of operations.

Note that each operation is effectively an adjacent transposition (swapping two adjacent elements) but the pair swapped is decided by the condition based on the first and the third chosen elements. In other words, you can simulate adjacent swaps with a careful choice of triples. Also note that since each operation swaps two elements (a transposition), if you denote by \(\mathrm{sgn}(p)\) the parity of the permutation then the parity of the number of operations must be consistent with \(\mathrm{sgn}(p)\) (because \(\mathrm{sgn}(\text{identity})=+1\)).

inputFormat

The first line contains two integers \(n\) and \(L\) \((1 \le n \le 8,\; 0 \le L \le 10^5)\) — the number of swallows and the maximum allowed number of operations.

The second line contains \(n\) distinct integers \(p_1, p_2, \dots, p_n\), which is a permutation of \(\{1, 2, \dots, n\}\).

outputFormat

If it is impossible to sort the permutation within at most \(L\) operations, output -1.

Otherwise, on the first line output an integer \(m\) (\(0 \le m \le L\)) representing the number of operations used. Each of the following \(m\) lines should contain three integers \(i, j, k\) \((1 \le i < j < k \le n)\) denoting one operation.

sample

3 10
1 2 3

0