B. Byte Pair Encoding
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array that initially consists of bytes (that is, integers between $$$0$$$ and $$$255$$$, inclusive). Let us define an occurrence of a pair of numbers $$$(l, r)$$$ in the array as a pair of indices $$$(i, i + 1)$$$ such that $$$a_i = l$$$ and $$$a_{i + 1} = r$$$.

You are to perform the following encoding process on this array:

  1. Pick a pair of distinct numbers $$$(l, r)$$$ that has the most occurrences in the current array. If there are several such pairs, choose the one with the smallest $$$l$$$; among those, select the one with the smallest $$$r$$$.
  2. Suppose $$$(l, r)$$$ has $$$q$$$ occurrences. If $$$q \lt 2$$$, stop the process. Otherwise, perform a bulk erasure operation as follows:

    For all $$$q$$$ occurrences of $$$(l, r)$$$ simultaneously, erase the numbers in them and write the number $$$255 + i$$$ in the place where the occurrence was located, if this erasure operation is the $$$i$$$-th ($$$i \ge 1$$$). The length of the array will decrease by $$$q$$$.

  3. If the bulk erasure operation has already occurred $$$k$$$ times, stop the process. Otherwise, go to step 1.

After the process ends, report the erasure operations you have performed, as well as the final array.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50\,000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100\,000$$$, $$$1 \le k \le n$$$): the initial array size and the maximum number of process iterations.

The second line contains $$$n$$$ integers between $$$0$$$ and $$$255$$$: the elements of the initial array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100\,000$$$.

Output

For each test case, in the first line, print an integer $$$e$$$ ($$$0 \le e \le \min\{k, n - 1\}$$$): the number of bulk erasure operations performed.

In the $$$i$$$-th of the next $$$e$$$ lines, print three integers $$$l$$$, $$$r$$$, $$$q$$$ ($$$0 \le l, r \le 254 + i$$$, $$$l \ne r$$$, $$$2 \le q \le n - 1$$$), denoting that the $$$i$$$-th bulk erasure operation was performed on a pair of numbers $$$(l, r)$$$, erasing it $$$q$$$ times.

The last line must contain the final $$$n - \sum q$$$ elements of the array. Every element must be an integer between $$$0$$$ and $$$255 + e$$$.

Example
Input
2
7 7
1 2 1 3 1 2 1
4 1
16 10 20 24
Output
2
1 2 2
256 1 2
257 3 257
0
16 10 20 24