题目描述

$5G$ 是拟议的下一代电信标准，超越当前的 $4G$ 标准。$5G$ 规划的目标是提供比当前 $4G$ 更高的容量，支持更高密度的移动宽带用户，并支撑设备到设备、高可靠和大规模的无线通信。一家电信公司希望安装更多基站，为客户提供更好的通信服务。由于安装成本和可选位置的限制，该公司只能在 $L$（$2 \le L \le 100,000$）个候选位置中安装 $S$（$2 \le S \le L$）个基站。由于这些基站工作在相同的频段，它们之间会产生干扰，导致严重的性能下降。为了向客户提供高质量的通信体验，公司希望最大限度地增大基站之间的距离，以减少基站间的无线干扰。假设 $L$ 个候选位置分布在一条直线上，坐标分别为 $P_1, P_2, \dots, P_L$（$0 \le P_i \le 1,000,000$），公司要从这些候选位置中选出 $S$ 个来安装基站。问这 $S$ 个基站所能达到的最大最小距离是多少？

输入格式

输入包含多组测试数据。

每组数据以一行开始，包含两个整数 $L$（候选位置数量）和 $S$（要安装的基站数量）。紧接着的一行包含 $L$ 个用空格分隔的整数，表示 $P_1, P_2, \dots, P_L$。输入以 “$0$ $0$” 结束。

输出格式

对于每组测试数据，你需要输出一行，即基站之间所能达到的最大最小距离。

对于第一组数据，$3$ 个基站可以安装在坐标 $2, 6, 11$ 的位置。

5 3
2 3 9 6 11
4 3
1 4 9 10
0 0

4
3

提示

翻译由 DeepSeek V4 Pro 完成