310511: CF1844F1. Min Cost Permutation (Easy Version)

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

The only difference between this problem and the hard 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^3$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $c$ ($1 \le n \le 5 \cdot 10^3$, $-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 $5 \cdot 10^3$.

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, ..., a_n，以及一个（可能为负）整数c。

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

序列x在字典序上小于序列y当且仅当以下条件之一成立：
- x是y的前缀，但x ≠ y；
- 在x和y的第一个不同的位置上，序列x的元素小于对应的y中的元素。

输入输出数据格式：
每个测试包含多个测试用例。第一行包含测试用例数t（1 ≤ t ≤ 10^3）。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数n和c（1 ≤ n ≤ 5 × 10^3，-10^9 ≤ c ≤ 10^9）。

每个测试用例的第二行包含n个整数a_1, ..., a_n（1 ≤ a_i ≤ 10^9）。

保证所有测试用例的n之和不超过5 × 10^3。

对于每个测试用例，输出n个整数b_1, ..., b_n，即达到最小\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|的字典序最小的排列b。

示例：
输入：
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。
在第二个测试用例中，\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|的最小可能值是0，b = [1,3,5]是达到这个最小值的字典序最小的排列a。
在第三个测试用例中，只有一个排列b。题目大意： 这个问题与难题版本的区别仅在于对t和n的限制。 给定一个包含n个正整数的数组a_1, ..., a_n，以及一个（可能为负）整数c。 在数组a_1, ..., a_n的所有排列b_1, ..., b_n中，考虑使\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|达到最小的排列b。找到达到这个最小值的字典序最小的排列b。 序列x在字典序上小于序列y当且仅当以下条件之一成立： - x是y的前缀，但x ≠ y； - 在x和y的第一个不同的位置上，序列x的元素小于对应的y中的元素。 输入输出数据格式： 每个测试包含多个测试用例。第一行包含测试用例数t（1 ≤ t ≤ 10^3）。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数n和c（1 ≤ n ≤ 5 × 10^3，-10^9 ≤ c ≤ 10^9）。 每个测试用例的第二行包含n个整数a_1, ..., a_n（1 ≤ a_i ≤ 10^9）。 保证所有测试用例的n之和不超过5 × 10^3。 对于每个测试用例，输出n个整数b_1, ..., b_n，即达到最小\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|的字典序最小的排列b。 示例： 输入： 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。 在第二个测试用例中，\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|的最小可能值是0，b = [1,3,5]是达到这个最小值的字典序最小的排列a。 在第三个测试用例中，只有一个排列b。