CF2008H.Sakurako's Test

Sakurako 即将参加一场考试，这场考试可用一个整数数组 $n$ 和一个相关任务来描述：

对于给定的整数 $x$，Sakurako 可以多次执行以下操作：

• 选择一个整数 $i$，其中 $1 \le i \le n$，且满足 $a_i \ge x$；
• 将 $a_i$ 的值减少 $x$，即改为 $a_i - x$。

通过这样的操作，她需要找到数组 $a$ 的最小可能中位数 $^{\text{∗}}$。

Sakurako 已知数组的内容，但不清楚整数 $x$ 的值。不过，有人透露在接下来的考试中，$x$ 的值会是给定的 $q$ 个值之一，因此她希望你能帮忙找出每一个可能的 $x$ 所对应的最小中位数。

$^{\text{∗}}$ 对于一个长度为 $n$ 的数组，若 $n$ 是偶数，则中位数是排序后数组中第 $\frac{n+2}{2}$ 个位置的元素；若 $n$ 是奇数，则为第 $\frac{n+1}{2}$ 个位置的元素。

第一行包含一个整数 $t$，表示测试用例的数量（$1 \le t \le 10^4$）。

接下来，每个测试用例的第一行包括两个整数 $n$ 和 $q$，分别表示数组的元素数量和查询数量（$1 \le n, q \le 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组的内容（$1 \le a_i \le n$）。

接下来的 $q$ 行每行给出一个整数 $x$，表示一个查询（$1 \le x \le n$）。

保证所有测试用例中 $n$ 和 $q$ 的总和均不超过 $10^5$。

对于每个测试用例，输出 $q$ 个整数，代表每个查询下计算出的答案。

本翻译由 AI 自动生成