Optimal separation P50778

Consider the sequence $1, 2, \dots, n$. If we use $k$ separators among those numbers, we get $k + 1$ subsequences. Let $s_i$ be the sum of the elements of the $i$-th subsequence. Let $m$ be the minimum $s_i$, and let $M$ be the maximum $s_i$. Given $n$ and $k$, please choose where to place the $k$ separators so that $M - m$ is as small as possible.

Input

Input consists of several cases, each one with $n$ and $k$. You can assume $1 \le n \le 50$ and $0 \le k \le \min(n - 1, 10)$.

Output

For every case, print $k + 3$ lines. On the first line print the minimum $M - m$. Afterwards, print a line for each of the $k + 1$ subsequences, in order, with the numbers and their sum. Finally, print a line with 10 dashes. Follow exactly the format of the sample output. If there is more than one optimal solution, choose any one.

Observation

The expected solution is a dynamic programming. This problem could also be solved by precomputing the solutions. But, if you do that, your solution will be manually rejected.