25000번 - Impressive Graphs 스페셜 저지다국어

문제

One of Sophie's tasks as a sales department employee is creating graphs of sales volumes. She has access to all the data, namely the integer sales volumes from the last $n$ months. Having glanced at the figures already, she knows that these numbers are pairwise different. The snag is that Sophie's boss expects impressive graphs, and not one but $k$ of them! A graph is impressive if the sequence of sales volumes in it is increasing. While Sophie can create empty graphs, she cannot get too creative. Namely, she has to conform with the following rules:

• any month's sales volume can be used in at most one graph;
• each graph must be in chronological order, i.e., for each pair of months in the graph, the earlier of the two months (and its corresponding sales volume) comes first.

The more sales volumes are used in a set of graphs, the more impressive it is.

Help Sophie in finding the most impressive set of $k$ graphs. That is, write a program that will: read the number of sales volumes, the number of sales graphs to be created, and the monthly sales volumes themselves, determines the most impressive set of sales graphs, and prints it to the standard output. If the most impressive set of sales graphs is not unique, your program may choose any of them.

입력

In the first line of input, there are two integers $n$ and $k$ (1ドル \le n \le 200,000円,ドル 1ドル \le k \le 20$), separated by a single space. These specify the number of sales volumes and the number of graphs, respectively. In the second (and last) line of input, there are $n$ pairwise different integers $a_1, a_2, \ldots, a_n$ (1ドル \leq a_i \leq n$), separated by single spaces. These are the sales volumes from successive months.

출력

Your program should print exactly $k+1$ lines. The first line should contain a single integer: the maximum number of sales volumes that can be used in a set of $k$ impressive graphs. The next $k$ lines should describe those graphs, one per line. A single description should consist of an integer $\ell$ ($\ell \geq 0$) --- the number of sales volumes in the graph --- followed by these volumes, i.e., $\ell$ integers $a_{i_1}, a_{i_2}, \ldots, a_{i_{\ell}}$ such that $i_1 < i_2 < \ldots < {i_\ell}$ and $a_{i_1} < a_{i_2} < \ldots < a_{i_\ell}$. All these numbers are separated by single spaces.

제한

노트

In first sample, the plots in the most impressive set of plots both have 2ドル$ sales volumes: 1,ドル 2$ in one plot and 4,ドル 5$ in the other.