B'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: 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 cdot 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 cdot 10^5 . For each test case, output n integers b_1, ... ,b_n , the lexicographically smallest permutation of a that achieves the minimum sum limits_{i=1}^{n-1} |b_{i+1}-b_i-c| . 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 . '...