Minimize Maximum Difference in Partitioning

You are given a conveyor belt consisting of M cells, each with a given height. Your task is to partition the belt into K contiguous sections (after sorting the heights) so that the maximum difference in height within any section is minimized. More formally, if each section contains a set of cells, let \( \Delta H \) be defined as:

[ \Delta H = \max(\text{section}) - \min(\text{section}) ]

You need to partition the sorted cell heights into K groups such that the maximum \( \Delta H \) amongst all groups is as small as possible. The input ends with a line "0 0" which should not be processed.

Note: Although the cells appear in a fixed order, you are allowed to sort the heights before forming the groups to achieve an optimal partitioning.

inputFormat

The input is given from standard input (stdin) and consists of several test cases. Each test case has two lines:

• The first line contains two positive integers \(M\) and \(K\): the number of cells and the number of sections, respectively.
• The second line contains \(M\) integers representing the heights of the cells.

The input terminates with a line containing "0 0", which should not be processed.

outputFormat

For each test case, output the minimum possible maximum difference \(\Delta H\) (in a separate line) achieved by an optimal partitioning of the cells.

## sample

7 3
10 5 7 9 12 6 3
6 2
1 2 3 4 5 6
4 2
10 20 30 40
0 0

3
2
10

</p>