← 返回题目列表

Codeforces · 2167/E

E. khba 爱睡觉!

中文机器翻译题面 查看原题

khba 有 $$$n$$$ 个朋友,每个朋友都站在位置 $$$a_i$$$ 的线上,并且每个人都在 $$$[0, x]$$$ 范围内。

他们都想来找他。他的一位朋友 Isamatdin 给了他 $$$k$$$ 传送。每个朋友都会步行到最近的传送点(选择最短的距离)。一旦朋友到达传送点,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$$$) — khba 朋友的位置。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

保证所有测试用例的 $$$k$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一行包含 $$$k$$$ 整数 - $$$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。 位置为 $$$[1,0,2,4]$$$ 的好友。选择的传送位置:$$$[3]$$$。

每个好友的最近传送时间为 $$$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]$$$。