Optimal separation P50778

Consider the sequence 1, 2, …, 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 ≤ n ≤ 50 and 0 ≤ k ≤ 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.