CF2167E khba Loves to Sleep!

khba 有 $n$ 个朋友，每个人都站在一条线上，其位置为 $a_i$，且每个人的位置都在 $[0, x]$ 区间内。 他们都想要来到 khba 身边。其中，有一个朋友 Isamatdin 给了 khba $k$ 个传送装置（teleport）。每个人会选择距离自己最近的传送装置（选择距离最近的那个）行走过去。当朋友到达传送装置时，khba 和这个朋友就可以立刻见面。 但是 khba 太累了，在朋友们走过来的时候他会一直睡觉。现在，他希望选择 $k$ 个传送装置的位置，使得这些位置互不相同且都位于区间 $[0,x]$ 内，从而最大化最先到达传送装置的朋友所需要的时间。假设所有朋友的移动速度相同。 由于 khba 不擅长计算，你需要输出选择的 $k$ 个传送装置的位置。

每个测试包含多组数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。接下来是各组数据的描述。 每组数据的第一行包含三个整数 $n$，$k$ 和 $x$（$1 \leq n, k \leq 2 \cdot 10^5$，$k-1 \leq x \leq 10^9$）——朋友数量、需要选择的传送装置数量和传送装置可选位置的区间范围。 每组数据的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq x$）——朋友们所在的位置。 保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。 保证所有测试数据中 $k$ 的总和不超过 $2 \cdot 10^5$。

每组测试用例输出一行，包含 $k$ 个整数，表示所选择的传送装置的位置。这些位置必须互不相同且都在区间 $[0, x]$ 内。输出顺序可以任意。 如果有多种最优方案，可以任选一种输出。

样例 1：朋友位置为 $[1,0,2,4]$，选择传送装置位置 $[3]$。 每个朋友距离最近传送装置的最短时间分别为 $[2, 3, 1, 1]$。 样例 2：朋友位置为 $[0,1,2,3,4]$，选择传送装置位置 $[0,1,2,3,4]$。 每个朋友距离最近传送装置的最短时间均为 $[0, 0, 0, 0, 0]$。 样例 3：朋友位置为 $[4,0]$，选择传送装置位置 $[2]$。 每个朋友距离最近传送装置的最短时间都是 $[2, 2]$。 样例 4：朋友位置为 $[2,4,3]$，选择传送装置位置 $[0,1,5,6]$。 每个朋友距离最近传送装置的最短时间分别为 $[1, 1, 2]$。 样例 5：朋友位置为 $[6,12,0]$，选择传送装置位置 $[3,9]$。 每个朋友距离最近传送装置的最短时间都是 $[3, 3, 3]$。 由 ChatGPT 5 翻译