write a go solution for Description:
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,...,a_n, and a (possibly negative) integer c.

Across all permutations b_1,...,b_n of the array a_1,...,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 xney;
- in the first position where x and y differ, the sequence x has a smaller element than the corresponding element in y.

Input Format:
Each test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10^4). The description of the test cases follows.

The first line of each test case contains two integers n and c (1<=n<=2*10^5, -10^9<=c<=10^9).

The second line of each test case contains n integers a_1,...,a_n (1<=a_i<=10^9).

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

Output Format:
For each test case, output n integers b_1,...,b_n, the lexicographically smallest permutation of a that achieves the minimum sumlimits_i=1^n-1|b_i+1-b_i-c|.

Note:
In the first test case, it can be proven that the minimum possible value of sumlimits_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 sumlimits_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.. Output only the code with no comments, explanation, or additional text.