F2. Перестановка минимальной стоимости (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между этой задачей и простой версией — в ограничениях на $$$t$$$ и $$$n$$$.

Вам дан массив из $$$n$$$ положительных целых чисел $$$a_1,\dots,a_n$$$, а также целое (возможно, отрицательное) число $$$c$$$.

Среди всех возможных перестановок $$$b_1,\dots,b_n$$$ массива $$$a_1,\dots,a_n$$$, рассмотрим минимально возможное значение $$$$$$\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|.$$$$$$ Найдите лексикографически наименьшую перестановку $$$b$$$ массива $$$a$$$, на которой достигается этот минимум.

Последовательность $$$x$$$ лексикографически меньше последовательности $$$y$$$, если и только если выполняется один из следующих пунктов:

  • $$$x$$$ — префикс $$$y$$$, но $$$x \ne y$$$;
  • в первой позиции, где $$$x$$$ и $$$y$$$ различны, в последовательности $$$x$$$ находится элемент, меньший соответствующего элемента $$$y$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа: $$$n$$$ и $$$c$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$-10^9 \le c \le 10^9$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,\dots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$b_1,\dots,b_n$$$, задающих лексикографически наименьшую перестановку $$$a$$$, на которой достигается минимум $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$.

Пример
Входные данные
3
6 -7
3 1 4 1 5 9
3 2
1 3 5
1 2718
2818
Выходные данные
9 3 1 4 5 1
1 3 5
2818
Примечание

В первом наборе входных данных можно доказать, что минимальное значение $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$ равно $$$27$$$, а перестановка $$$b = [9,3,1,4,5,1]$$$ является лексикографически наименьшей перестановкой $$$a$$$, на которой достигается этот минимум: $$$|3-9-(-7)|+|1-3-(-7)|+|4-1-(-7)|+|5-4-(-7)|+|1-5-(-7)| = 1+5+10+8+3 = 27$$$.

Во втором наборе входных данных минимально возможное значение $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$ равно $$$0$$$, при этом $$$b = [1,3,5]$$$ является лексикографически наименьшей перестановкой $$$a$$$, на которой достигается этот минимум.

В третьем наборе входных данных существует всего одна перестановка $$$b$$$.