# [Solution] Adjacency Love solution codechef

Adjacency Love solution codechef – An array is called lovely if the sum of product of each adjacent pair of elements is odd.

More formally, the array SS of size MM is lovely if the value M1i=1∑i=1M−1 (Si.Si+1)(Si.Si+1) is odd.

You are given an array AA consisting of NN positive integers. Find a permutation of array AA which is lovely.

If multiple such permutations are possible, output any. If there is no lovely permutation, output -1.

### Input Format

• 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, if a lovely permutation of AA is possible, print a single line containing NN integers denoting the elements of any lovely permutation of AA. Otherwise, print -1.

### Constraints

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

• Subtask 1 (100 points): Original constraints.

### Sample Input 1

2
5
1 2 3 4 10
3
7 11 145


### Sample Output 1

3 1 10 2 4
-1