Min Cost Permutation (Easy Version)
Contest: Codeforces Round 884 (Div. 1 + Div. 2)
Difficulty rating: 2600
Tags: brute force, constructive algorithms, greedy, math

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 format:
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 format:
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|$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
3
6 -7
3 1 4 1 5 9
3 2
1 3 5
1 2718
2818

Example output:
9 3 1 4 5 1
1 3 5
2818

Editorial:
Let the cost of a permutation $$$b$$$ of $$$a$$$ be the value $$$\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$.
When $$$c \ge 0$$$, it can be proven that the minimum cost can be obtained by sorting $$$a$$$ in nondecreasing order. As sorting $$$a$$$ in nondecreasing order is also the lexicographically smallest array, this is the answer.
Similarly, when $$$c < 0$$$, it can be proven that the minimum cost can be obtained by sorting $$$a$$$ in nonincreasing order. Furthermore, if we have fixed the values of $$$b_1,\dots,b_k$$$ for some $$$1 \le k < n$$$, then intuitively, one optimal permutation $$$b_{k+1},\dots,b_n$$$ of the remaining elements is to sort them in nonincreasing order$$$^\dagger$$$.
To find the lexicographically smallest permutation, we can greedily loop through $$$k = 1,\dots,n$$$, each time taking the smallest $$$b_k$$$ that does not increase the cost. If $$$a_k \ge \dots \ge a_n$$$ are the unused elements sorted in nonincreasing order, then the condition we need to check to determine if setting $$$b_k := a_i$$$ is good is whether $$$|a_{i-1}-a_i-c|+|a_i-a_{i+1}-c|+|b_{k-1}-a_k-c| \ge |a_{i-1}-a_{i+1}-c|+|b_{k-1}-a_i-c|+|a_i-a_k-c|\quad(*)$$$ (with some adjustments in the corner cases when $$$k = 1$$$ or $$$i = k,n$$$). This condition $$$(*)$$$ can be checked in constant time, and we try $$$\mathcal{O}(n)$$$ values of $$$i$$$ for each of the $$$\mathcal{O}(n)$$$ values of $$$k$$$, so the time complexity is $$$\mathcal{O}(n^2)$$$.
The proofs of the claims used in this solution can be found at the end of the solution for the hard version.
$$$^\dagger$$$This is actually not true as stated (e.g. when $$$c = -1$$$ and we fix $$$b_1 = 2$$$, $$$[2,1,9,8]$$$ is better than $$$[2,9,8,1]$$$), but it turns out it is true for all states that the greedy algorithm can reach (i.e. in this example, the greedy algorithm could not have chosen $$$b_1 = 2$$$).