EIU Programming Practices and Exams

Given an array of N integers, select K elements out of these N elements in such a way that the minimum difference between each of the K numbers is the largest. Your task is to print out the largest minimum difference after choosing any K elements.

Input

-      The first line contains two integers N, K (1 ≤ N ≤ 10⁵_, 2 ≤ K ≤ N).

-      The second line contains N integers.

All integers don’t exceed 10⁹

Output

The largest minimum difference after choosing K elements from N elements.

Sample

Note: 50% testcases have K = 2, 3, or 4

Explanation

First sample:

• Select 3 elements 2, 2, 5 will result in minimum difference as 0.
• Select 2, 5, 6 will result in minimum difference as 6 – 5 = 1 (since 5 – 2 = 3 and 6 – 2 = 4 are not the minimum difference), which is also the largest minimum difference.

Second sample:

• Select 0, 4, 9, 13 will result in minimum difference of 4, which is the largest minimum difference possible.