Derangement Permutation

This problem requires you to compute a derangement of a given array. A derangement is a permutation in which no element stays at its original position. Formally, given an array \(a\), you need to rearrange its elements into an array \(b\) such that for every index \(i\), \(b_i \neq a_i\). If such a rearrangement is not possible, simply output -1.

Important: A derangement does not exist for an array of size one, or if any element appears more than \(\frac{n}{2}\) times (i.e. more than half of the array elements). You will be given multiple test cases. For each test case, the first number denotes the number of elements in the array, followed by the elements of the array.

inputFormat

The input begins with an integer \(T\) (the number of test cases). Each test case starts with an integer \(N\) (the number of elements), followed by \(N\) integers separated by spaces.

Example:

3
4
1 2 3 4
3
1 1 1
6
1 2 3 1 2 3

outputFormat

For each test case, output a single line. If a valid derangement exists, print the deranged array (elements separated by a space). Otherwise, output -1.

## sample

3
4
1 2 3 4
3
1 1 1
6
1 2 3 1 2 3

2 3 4 1
-1
2 1 2 3 3 1

</p>