Problem

You are given an array �A of size �N.
Let �B denote the array obtained by sorting �A in increasing order, and �C denote the array obtained by sorting �A in decreasing order.

Table of Contents

Consider all permutations �D, of the array �A, such that �D is not equal to �B and �D is not equal to �C.

We define the score of such �D as: min(∣��−�(�−1)∣)min(∣Di−D(i−1)∣) , for (1<�≤�)(1<i≤N).

Output a �D with minimum possible score.
If multiple such permutations of the array �A exist, print any. If no permutation exists, output −1−1 instead.

Input Format

The first line of input will contain a single integer �T, denoting the number of test cases.
Each test case consists of multiple lines of input.
- The first line of each test case contains single integer �N — the size of the array.
- The next line contains �N space-separated integers, denoting the array �A.

Output Format

For each test case, output on a new line, �N space-separated integers, a permutation of array �A that satisfies the given conditions, and has the minimum score.

If multiple such permutations of the array �A exist, print any. If no permutation exists, output −1−1 instead.

Constraints

1≤�≤2001≤T≤200
2≤�≤1052≤N≤105
1≤��≤1091≤Ai≤109
The sum of �N over all test cases won’t exceed 2⋅1052⋅105.

Sample 1:

Input

Output

2 1 3
3 3 1 5
2 1 4 3

Explanation:

Test case 11: The given array �=[2,1,3]A=[2,1,3] is not sorted in increasing or decreasing order. Also, the score of �A is min(∣��−�(�−1)∣)=min(1,2)=1min(∣Ai−A(i−1)∣)=min(1,2)=1. It can be proven that this is the minimum score that can be obtained.

Test case 22: Consider the permutation �=[3,3,1,5]D=[3,3,1,5]. This is not sorted in increasing or decreasing order. Also, the score of �D is min(∣��−�(�−1)∣)=min(0,2,4)=0min(∣Di−D(i−1)∣)=min(0,2,4)=0. It can be proven that this is the minimum score that can be obtained.

Test case 33: Consider the permutation �=[2,1,4,3]D=[2,1,4,3]. This is not sorted in increasing or decreasing order. Also, the score of �D is min(∣��−�(�−1)∣)=min(1,3,1)=1min(∣Di−D(i−1)∣)=min(1,3,1)=1. It can be proven that this is the minimum score that can be obtained.

More Info