There are n tasks (T1,…,Tn) that need to be executed exactly once. Each task requires the use of a common equipment in such a way that on a given day, Ti can be completed if and only if no task Tj (j > i) has been completed on that day. In other words, the set of tasks completed on each day must have increasing indices. An additional constraint is imposed because of task categories: each task Ti belongs to category Ci, and tasks Ti, Tj cannot be scheduled consecutively on a particular day if they belong to nearby categories, i.e., if |Ci - Cj| <= K.
What is the smallest number of days needed to complete all the tasks? Also output the indexes of the tasks that should be executed on each day.
Please add a short paragraph explaining the approach at the beginning of the code to help us better understand and evaluate the solution. Also, try to keep the code readable (with comments) so that it is easier to evaluate the code correctness.
Input Format
Line 1: Space separated integers: n and K
Line 2,…,n+1: Line i+1 lists the integer Ci
Constraints
1 <= n <= 1000, 1 <= Ci <= 100000
Output Format
Least number of days required to complete all the tasks on the first line. If the answer is D, then it should be followed by D lines where each line lists the tasks to be executed on that day.
Sample Input
5 2
15
9
12
15
18
Sample Output
1
1 2 3 4 5
Sample Input
5 3
1
2
7
5
2
Sample Output
2
1 4
2 3 5
Explanation
All the tasks can be done in their original sequence in one day since two consecutive tasks have difference 3 (> 2).