Hard Game

Input

The first line contains an integer $t$ (1 \le t \le 10^4) — the number of test cases.

Each test case consists of two lines:

The first line contains a single integer n(1 \le n \le 2 \cdot 10^5) — the length of the array.

The second line contains $n$ integers a_{1},a_{2},…,a_{n} (-10^9 \le a_{i} \le 10^9) — the points that he will gain after each round.

It is guaranteed that the sum of $n$ across all test cases does not exceed 2 \cdot 10^5.

Output

For each test case, output any permutation of the array $a$ — b_1,b_2,b_3,...,b_n that achieves the maximum value of total points Fateh gets.

If such permutation doesn't exist output $-1$.

Examples

Note

The result of first test case goes as following :

1. Fateh gets $5$ points , Total: $5$ points.

2. Fateh gets $3$ points , Total of $8$ points.

3. Fateh gets $2$ points , Total of $10$ points.

4. Fateh gets $-1$ points , He gets angry and has a score of $9$ , Now he'll skip the next two games , and since no game remains he cannot play anymore.

The maximum score he gains is $9$.

Scoring

1. Subtask $1$ ($20$ points) : (1 \le n \le 8) and (1 \le t \le 100)

2. Subtask $2$ ($30$ points) : (0 \le a_i \le 10^9)

3. Subtask $3$ ($150$ points) : No additional constraints