Description

共有 $n$ 个风铃悬挂在屋檐下，每个风铃都能发出一定音调的声音。从左到右给风铃从 $1$ 至 $n$ 编号，第 $i$ 个风铃的音调是 $a_i$。

为了表达内心的思念，扶苏决定在 $n$ 个的风铃中取出 $m$ 个，送给远方的朋友。

请你找到最小的整数 $\varepsilon$，使得存在一种方案，能够从 $n$ 个风铃中挑出 $m$ 个，设挑出风铃的音调为 $b_1, b_2, \dots b_m$，满足对任意的 $1 \leq i, j \leq m$，都有 $|b_i - b_j| \leq \varepsilon$。

Input Format

第一行是两个整数，表示风铃的个数 $n$ 和挑选出风铃的个数 $m$。
第二行有 $n$ 个整数，表示每个风铃的音调。第 $i$ 个整数表示 $a_i$。

Output Format

输出一行一个整数，表示最小的 $\varepsilon$。

5 3
1 2 3 4 5

2

6 4
1 7 8 3 4 6

4

Hint

样例 2 解释

一种选择的方案是选择第 $2,4,5,6$ 四个风铃，音调依次为 $7,3,4,6$。可以得到对任何的 $1 \leq i, j\leq 4$，都有 $|b_i - b_j| \leq 4$。

另一种方案是选择第 $2,3,5,6$ 四个风铃，同样计算得到的 $\varepsilon$ 为 $4$。

数据规模与约定

• 对 $10\%$ 的数据，$m = 2$。
• 另有 $10\%$ 的数据，$m = n$。
• 对 $40\%$ 的数据，$n \leq 5$。
• 对 $60\%$ 的数据，保证对所有的 $2 \leq i \leq n$，满足 $a_{i - 1} \leq a_i$，即 $a_i$ 单调不降。
• 对 $80\%$ 的数据，$n \leq 10^3$。
• 对 $100\%$ 的数据，$2 \leq m \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$。

说明

本题共有三个附加样例文件，见题目附件中的 ring.zip。