题目描述

有 $n$ 个朋友站在一条数轴上，第 $i$ 个朋友的位置为 $a_i$，所有位置都在区间 $[0,x]$ 内。

你需要选择 $k$ 个互不相同的传送点位置，位置也必须在 $[0,x]$ 内。

每个朋友会走向离自己最近的传送点。请你选择这 $k$ 个传送点，使得“最先到达传送点的朋友”所需时间尽可能大。

也就是说，需要最大化所有朋友到最近传送点距离中的最小值。

如果有多种最优方案，输出任意一种。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据包含两行：

第一行三个整数 $n,k,x$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示朋友的位置。

保证所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$，$k$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每组测试数据，输出一行 $k$ 个整数，表示选择的传送点位置。

这些位置必须互不相同，且都在 $[0,x]$ 内。可以按任意顺序输出。

样例

10
4 1 4
1 0 2 4
5 5 4
0 1 2 3 4
2 1 4
4 0
3 4 6
2 4 3
3 2 12
6 12 0
4 3 12
8 12 0 4
1 1 1000000000
0
1 1 1000000000
1000000000
3 4 9
8 7 9
3 4 9
2 0 1

3
0 1 2 3 4
2
0 1 5 6
3 9
2 6 10
1000000000
0
0 1 2 3
6 7 8 9

样例说明

样例输出只是其中一种最优方案，顺序也可以不同。

第一组测试数据中，朋友位置为 $[1,0,2,4]$，选择传送点 $[3]$。每个朋友到最近传送点的距离分别为 $[2,3,1,1]$。

第二组测试数据中，朋友位置为 $[0,1,2,3,4]$，选择传送点 $[0,1,2,3,4]$。所有朋友到最近传送点的距离都是 $0$。

第三组测试数据中，朋友位置为 $[4,0]$，选择传送点 $[2]$。两个朋友到传送点的距离都是 $2$。

第四组测试数据中，朋友位置为 $[2,4,3]$，选择传送点 $[0,1,5,6]$。三个朋友到最近传送点的距离分别为 $[1,1,2]$。

第五组测试数据中，朋友位置为 $[6,12,0]$，选择传送点 $[3,9]$。三个朋友到最近传送点的距离都是 $3$。

数据范围

• $1 \le t \le 10^4$
• $1 \le n,k \le 2\cdot 10^5$
• $k-1 \le x \le 10^9$
• $0 \le a_i \le x$
• 所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$
• 所有测试数据的 $k$ 之和不超过 $2\cdot 10^5$

来源

Codeforces Round 1062 (Div. 4), Problem E - khba Loves to Sleep!