P17651 [IO 2025 #1] 避难所

一根绷紧的丝线横跨法鲁姆，$n$ 个小居民住在这根丝线上。第 $i$ 个居民位于坐标 $x_i$。需要在线上设置一些茧，作为他们的避难所。 设置好茧之后，每个居民都会前往距离自己最近的避难所。也就是说，若这些茧的坐标为 $a_1,\ldots,a_k$，则对每个 $x_i$，选择使 $|x_i-a_{j_i}|$ 最小的 $j_i$。这组茧的**危险程度**定义为 $D=\max_{i=1}^n|x_i-a_{j_i}|$，即居民到最近避难所的距离的最大值。 黄蜂收到 $q$ 项相互独立的委托。每项委托指定： - 一个整数 $k$，表示最终需要在线上设置的茧状避难所总数； - 一个整数 $r$ 和一组坐标 $a_1,\ldots,a_r$，表示其中 $r$ 个避难所已经确定的位置。 她需要再在线上的任意位置添加 $k-r$ 个避难所，使最终的危险程度尽可能小。新避难所的坐标不必是整数。 对每项委托，求最终危险程度的最小可能值。各项委托互不影响。

输入包含多组数据。第一行包含一个整数 $t$，表示数据组数，满足 $1\le t\le5000$。接下来依次给出各组数据。 每组数据的第一行包含两个整数 $n,q$，分别表示居民数和委托数，满足 $1\le n,q\le35000$。 第二行包含 $n$ 个整数 $x_i$，表示居民的坐标，满足 $|x_i|\le10^8$。 接下来 $q$ 行描述各项委托。每行依次包含整数 $k,r,a_1,\ldots,a_r$，其中 $k$ 是最终的避难所总数，$r$ 是已经确定位置的避难所数，$a_j$ 是这些避难所的坐标，满足 $1\le k\le35000$，$0\le r\le k$，$|a_j|\le10^8$。 保证所有数据组的 $n\cdot q$ 之和不超过 $35000$，所有委托的 $r$ 之和不超过 $35000$。

对每组数据输出一行，包含 $q$ 个实数，依次表示各项委托的答案。如果某个输出答案与标准答案之间的绝对误差或相对误差不超过 $10^{-9}$，则认为该答案正确。

对于第一组数据： 1. 第一个委托只需要设置一个避难所，应将它放在最左、最右两个居民的位置 $-5$ 和 $11$ 的中点。这两个居民到避难所的距离均为 $8$。 2. 第二个委托可以将两个避难所分别放在 $-5$ 与 $0$ 的中点，以及 $4$ 与 $11$ 的中点。 3. 第三个委托可以将避难所放在 $-3$、$2$ 和 $10$。 4. 第四个委托只需在每个居民的位置设置一个避难所。 5. 第五个委托只需将第二个避难所设置在坐标 $10$ 和 $11$ 的居民附近，此时最大的距离是坐标 $-5$ 的居民到坐标 $0$ 的避难所的距离。 6. 第六个委托可以在坐标 $10$ 和 $11$ 附近添加一个避难所，并在坐标 $-2.5$ 添加另一个。