这个问题和简单版本之间的唯一区别是对 $$$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$$$,$$$a$$$ 的字典顺序最小排列,实现最小 $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$。
示例
输入 #1
3 6 -7 3 1 4 1 5 9 3 2 1 3 5 1 2718 2818
输出 #1
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$$$。