310512: CF1844F2. Min Cost Permutation (Hard Version)

F2. Min Cost Permutation (Hard Version)time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The only difference between this problem and the easy version is the constraints on $t$ and $n$.

You are given an array of $n$ positive integers $a_1,\dots,a_n$, and a (possibly negative) integer $c$.

Across all permutations $b_1,\dots,b_n$ of the array $a_1,\dots,a_n$, consider the minimum possible value of $$\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|.$$ Find the lexicographically smallest permutation $b$ of the array $a$ that achieves this minimum.

A sequence $x$ is lexicographically smaller than a sequence $y$ if and only if one of the following holds:

• $x$ is a prefix of $y$, but $x \ne y$;
• in the first position where $x$ and $y$ differ, the sequence $x$ has a smaller element than the corresponding element in $y$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $c$ ($1 \le n \le 2 \cdot 10^5$, $-10^9 \le c \le 10^9$).

The second line of each test case contains $n$ integers $a_1,\dots,a_n$ ($1 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output $n$ integers $b_1,\dots,b_n$, the lexicographically smallest permutation of $a$ that achieves the minimum $\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$.

ExampleInput

3
6 -7
3 1 4 1 5 9
3 2
1 3 5
1 2718
2818

Output

9 3 1 4 5 1
1 3 5
2818

Note

In the first test case, it can be proven that the minimum possible value of $\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$ is $27$, and the permutation $b = [9,3,1,4,5,1]$ is the lexicographically smallest permutation of $a$ that achieves this minimum: $|3-9-(-7)|+|1-3-(-7)|+|4-1-(-7)|+|5-4-(-7)|+|1-5-(-7)| = 1+5+10+8+3 = 27$.

In the second test case, the minimum possible value of $\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$ is $0$, and $b = [1,3,5]$ is the lexicographically smallest permutation of $a$ that achieves this.

In the third test case, there is only one permutation $b$.

题目大意：
这个题目与简单版本的不同之处在于对t和n的限制。

给定一个由n个正整数组成的数组a_1, \dots, a_n，以及一个（可能是负的）整数c。

在数组a_1, \dots, a_n的所有排列b_1, \dots, b_n中，考虑\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|的最小可能值。找出达到这个最小值的数组a的字典序最小的排列b。

一个序列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，即达到最小\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|的数组a的字典序最小的排列。

示例：
输入：
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_{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_{i=1}^{n-1} |b_{i+1}-b_i-c|的最小可能值是0，b = [1,3,5]是达到这个最小值的数组a的字典序最小的排列。
在第三个测试案例中，只有一个排列b。题目大意： 这个题目与简单版本的不同之处在于对t和n的限制。 给定一个由n个正整数组成的数组a_1, \dots, a_n，以及一个（可能是负的）整数c。 在数组a_1, \dots, a_n的所有排列b_1, \dots, b_n中，考虑\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|的最小可能值。找出达到这个最小值的数组a的字典序最小的排列b。 一个序列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，即达到最小\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|的数组a的字典序最小的排列。 示例： 输入： 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_{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_{i=1}^{n-1} |b_{i+1}-b_i-c|的最小可能值是0，b = [1,3,5]是达到这个最小值的数组a的字典序最小的排列。 在第三个测试案例中，只有一个排列b。