题目描述

共有 $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$。

提示：$|b_i - b_j| \leq \varepsilon$ 的意思是，两个数的差距小于等于 $\varepsilon$。

输入格式

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

• 对 $100\%$ 的数据，$2 \leq m \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$。

输出格式

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

5 3
1 2 3 4 5

2

6 4
1 7 8 3 4 6

4

提示

样例 1 解释

选择第 $1,2,3$ 三个风铃，音调依次为 $1,2,3$，可以得到对任何的 $1≤i,j≤3$，都有 $|b_i - b_j| \leq 2$。 选择第 $2,3,4$ 和 $3,4,5$ 号风铃是一样的结果。

样例 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$。