U535992 J-C 小梦的宝石收集

小梦有 $n$ 颗能量宝石，其中第 $i$ 颗的能量为 $a_i$，但这些能量宝石十分不稳定，随时有可能发生崩坏，导致他们全部消失！ 小梦想要留住宝石们，不希望他们发生崩坏，同时他发现：如果这些宝石的能量的极差越大，则这些宝石们越不稳定，因此他希望最小化这些宝石的能量的极差（最大值减去最小值的差值）。 小梦有一招点石成金的技能，这个技能可以以如下方式改变一些宝石的能量： $\bullet$ 要么小梦选择一块能量最小的宝石，将他变成一块当前能量最大的宝石。 $\bullet$ 要么小梦选择一块能量最大的宝石，将他变成一块当前能量最小的宝石。 形式化的即： $\bullet$ 选择 $i\ (1 \leq i \leq n, a_i = min(a_1, a_2,...,a_n))$，执行：$a_i:=max(a_1, a_2,...,a_n)$。 $\bullet$ 或选择 $i\ (1 \leq i \leq n, a_i=max(a_1, a_2,...,a_n))$，执行：$a_i:=min(a_1, a_2,...,a_n)$。 小梦至多可以使用 $k$ 次上述的 ”点石成金“ 技能，他想知道这些宝石的能量极差最小可以变为多少，请你帮他算一算吧。

**本题有多组测试数据。** 输入的第一行包含一个正整数 $T$，表示数据组数。 接下来包含 $T$ 组数据，每组数据的格式如下： 第一行两个正整数 $n, k$，分别表示小梦拥有的宝石数量 $n$ ，和他最多可以释放 “点石成金” 技能的次数 $k$。 第二行 $n$ 个正整数 $a_i$，表示每块宝石的能量。

对于每组测试数据： 在单独的一行输出一个整数，表示宝石能量的极差最小值。

**【样例 1 解释】** 使用 $3$ 次操作一，选择 $min$ 变为 $max$，操作完后数组变成：$\{8,8,8,4,5,6,7,8\}$。 此时数组的极差为 $4$ 最小，可以证明不存在比 $4$ 更优的答案。 **【数据范围】** 令 $N$ 表示 $T$ 组数据中 $n$ 的总和。 对于 $30\%$ 的数据有：$T = 1, 1 \leq k \leq N\leq 20$。 对于 $\rm 60\%$ 的数据有：$1 \leq T \leq 10, 1 \leq k \leq N \leq 2000$。 对于所有的测试数据有： $1 \leq T \leq 1000, 1 \leq N \leq 5 \times 10^5, 0 \leq k \leq n, 0 \leq a_i \leq 10^9$。