P16326 星降る海


You are given a color sequence $a$ of length $n$ and a positive integer $k$. You may perform the following operation any number of times. - Choose a subset $S$ of $\{1,2,\ldots,n\}$ and a color $c$, then change the color of every position in $S$ to $c$. Determine the minimum number of operations needed to make the number of maximal color segments exactly $k$, and construct a solution. If there are multiple possible constructions, you may output any.

The first line contains two positive integers $n,k$. The second line contains $n$ positive integers $a_i$, denoting the color sequence.

Print the minimum number of operations $t$ on the first line. Then print $t$ lines describing the operations in order. For each line, the first integer $s_i$ denotes the size of the chosen set, followed by $s_i$ distinct integers between $1$ and $n$ indicating the elements of the set, and finally an integer $c$ between $1$ and $n$ denoting the new color.

**Constraints** For all test cases, $1\le k\le n\le 10^5$ and $1\le a_i\le n$. | Subtask | $n\le$ | Special Property | Score | | :-----: | :----: | :--------------: | :---: | | $1$ | $6$ | None | $20$ | | $2$ | $10^5$ | A | $20$ | | $3$ | $10^5$ | B | $20$ | | $4$ | $10^5$ | None | $40$ | - Special Property A: It is guaranteed that $k=1$. - Special Property B: It is guaranteed that $k=n$.