Fuel Stations

Fuel Stations

There are n candidate positions for fuel stations along a highway, given as integer coordinates ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​‌‌​​‌​‌​‌‌​​‌​​​​‌‌​​​​​​‌‌​​​​​‌‌​​‌​​​‌‌​​‌​‌​​‌‌‌​​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌​​‌​​​‌‌​‌​​​​‌‌​‌‌​​​‌‌‌​​​​​‌‌​‌‌‌(not necessarily sorted, not necessarily distinct... they are distinct in this problem). You must build exactly k of them. To keep the network robust, you want to maximize the minimum distance between any two built stations.

Input

Line 1: two integers n k (2 ≤ k ≤ n ≤ 10^5) ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​‌‌​​‌​‌​‌‌​​‌​​​​‌‌​​​​​​‌‌​​​​​‌‌​​‌​​​‌‌​​‌​‌​​‌‌‌​​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌​​‌​​​‌‌​‌​​​​‌‌​‌‌​​​‌‌‌​​​​​‌‌​‌‌‌Line 2: n integers, the candidate positions (0 ≤ x_i ≤ 10^9, all distinct)

Output

A single integer: the largest possible value of the minimum pairwise distance between the k chosen stations.

Example

Input:

5 3
​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​‌‌​​‌​‌​‌‌​​‌​​​​‌‌​​​​​​‌‌​​​​​‌‌​​‌​​​‌‌​​‌​‌​​‌‌‌​​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌​​‌​​​‌‌​‌​​​​‌‌​‌‌​​​‌‌‌​​​​​‌‌​‌‌‌1 2 8 4 9

Output:

3

Constraints

• 2 ≤ k ≤ n ≤ 10^5
• 0 ≤ x_i ≤ 10^9, all positions distinct ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​‌‌​​‌​‌​‌‌​​‌​​​​‌‌​​​​​​‌‌​​​​​‌‌​​‌​​​‌‌​​‌​‌​​‌‌‌​​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌​​‌​​​‌‌​‌​​​​‌‌​‌‌​​​‌‌‌​​​​​‌‌​‌‌‌

5 3
1 2 8 4 9

3

4 2
1 1000000000 500000000 250000000

999999999