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.

Public test cases

**Input**

4 0 50 10

**Output**

0 1 + 2 + 3 + 4 = 10 ---------- 40 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 = 120 16 + 17 + 18 + 19 + 20 + 21 + 22 = 133 23 + 24 + 25 + 26 + 27 = 125 28 + 29 + 30 + 31 = 118 32 + 33 + 34 = 99 35 + 36 + 37 = 108 38 + 39 + 40 = 117 41 + 42 + 43 = 126 44 + 45 + 46 = 135 47 + 48 = 95 49 + 50 = 99 ----------

Information

- Author
- Josep Grané
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Setzè Concurs de Programació de la UPC - Final
- Date
- 2018-09-19