Rearrange Sequence to Minimize Adjacent Difference

You are given one or more test cases. In each test case, you are provided a sequence of n integers. Your task is to rearrange the sequence so that the absolute difference between any two adjacent integers is minimized.

The problem can be mathematically described as follows: Given a sequence \(a_1,a_2,\dots,a_n\), find a permutation \(b_1,b_2,\dots,b_n\) such that the sum \(\sum_{i=1}^{n-1} |b_{i+1}-b_i|\) is as small as possible. It can be shown that sorting the sequence in non-decreasing order produces an optimal solution.

Example:
If the input sequence is: 4 2 1 3 5, the rearranged sequence is: 1 2 3 4 5.

inputFormat

The first line of the input contains a single integer T indicating the number of test cases. For each test case:

• The first line contains an integer n representing the number of integers in the sequence.
• The second line contains n space-separated integers.

All input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the rearranged sequence with the integers in non-decreasing order, separated by spaces. All output should be written to standard output (stdout).

## sample

3
5
4 2 1 3 5
4
-1 -2 -3 -4
3
2 1001 1000

1 2 3 4 5
-4 -3 -2 -1
2 1000 1001

</p>