Maximizing Minimum Happiness

Bessie received N chocolates with happiness values H_i (given in the order she received them) and she must finish eating all of them within D days. Her happiness level starts at 0 on day 1. Every day, after waking up, her happiness is the previous day's bedtime happiness halved (using floor‐division). Then, during the day she may eat some chocolates (following the original order) to raise her happiness. The day’s final (bedtime) happiness is the sum of her morning happiness and the total happiness from the chocolates eaten that day.

On each day except the last, Bessie may choose to eat chocolates only if her current happiness is less than a target value X (which represents a candidate for the minimum daily happiness). On the last day she is forced to eat all remaining chocolates. A schedule is valid only if for every day the bedtime happiness is at least X and all chocolates are eaten by the end of day D.

Your task is to find a schedule that maximizes this minimum daily happiness value. If more than one optimal solution exists, you may output any one of them.

Input Format:
The first line contains two integers N and D (1 ≤ N, D ≤ 5×10⁴).
The second line contains N integers, where the i-th integer is the happiness value H_i (1 ≤ H_i ≤ 10⁶) for the i-th chocolate.

Output Format:
On the first line, output the maximum possible minimum daily bedtime happiness that Bessie can achieve. Then output D lines describing the schedule. The i-th of these lines should start with an integer k – the number of chocolates eaten on that day – followed by k space‐separated integers representing the 1-indexed positions of the chocolates eaten that day.

Note on the Process:
Let cur be Bessie’s current happiness. At the start of day 1, cur = 0. For day 1 ≤ d < D, Bessie wakes up with floor(cur/2) happiness. If this value is less than a candidate threshold X, she may choose to eat some chocolates – as few as necessary – in order to make the day’s final happiness (morning happiness plus the sum of eaten chocolates) at least X. On day D she must eat all remaining chocolates. The schedule is valid if each day’s bedtime happiness is at least X and all chocolates are consumed by the end of day D.

inputFormat

The input consists of two lines. The first line contains two integers N and D. The second line contains N integers representing the happiness values of the chocolates in the order Bessie received them.

outputFormat

Output the maximum achievable minimum daily bedtime happiness on the first line. Then, output D lines - each line begins with an integer denoting the number of chocolates eaten on that day, followed by the list of chocolate indices (1-indexed) eaten on that day. If on a day no chocolate is eaten, output 0 on that line.

sample

5 5
10 40 13 22 7

24
2 1 2
0
1 3
1 4
1 5