E. khba любит спать!
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У 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]$$$, соответственно.