Contents

• # For Solution

An array is called lovely if the sum of absolute differences of each adjacent pair of elements is odd; formally, the array SS of size mm is lovely if m1i=1∑i=1m−1 |SiSi+1||Si−Si+1| is odd.

You are given an array AA of NN integers. You need to reorder the array in any manner such that the array becomes lovely. If there is no reordering operation that makes the array lovely, output -1.

• The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
• The first line of each test case contains an integer NN.
• The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

### Output Format

For each test case, print a single line containing NN integers denoting the modified array which is lovely, or -1 if it is not possible.

• 1T10001≤T≤1000
• 2N5002≤N≤500
• 1Ai1061≤Ai≤106

### Sample Input 1

2
6
3 7 10 1 2 12
2
1 3


1 2 3 10 7 12
-1


### Explanation

• For the first test case, the sum is |12|+|23|+|310|+|107|+|712|=1+1+7+3+5=17|1−2|+|2−3|+|3−10|+|10−7|+|7−12|=1+1+7+3+5=17 which is odd.

• For the second test case, |13|=2|1−3|=2 which is even. There is no array that can satisfy the above condition.