FIICode 2025 Qualifying Round - Studenți | No More Threes

Task

You are given an array $a$ of length $n$.

Find any array $b$ of length $n$ which satisfies all of the following conditions:

• $[b_1,b_2,\ldots,b_n]$ is a permutation$^1$ of $[a_1,a_2,\ldots,a_n]$;
• For all $i$ ($1 \le i \le n$), $b_1+b_2+b_3+\ldots+b_i$ is not divisibile by $3$.

If no such array exists, print -1 instead.

$^1$An array $[b_1,b_2,\ldots,b_n]$ is a permutation of another array $[a_1,a_2,\ldots,a_n]$ if $b$ contains the same elements as $a$, but potentially in another order. For example, $[1,2,3,3]$ is a permutation of $[3,2,3,1]$, but $[3,2,3,1]$ is not a permutation of $[2,2,3,1]$.

Input data

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) - the number of test cases. The next lines contain the descriptions of the test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) - the length of array $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) - the elements of array $a$.

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

Output data

For each test case, print any array $[b_1,b_2,\ldots,b_n]$ which satisfies all of the conditions from the statement.

If no such arrays exist, print -1 instead.

Example

stdin

7
1
1
4
2 2 2 2
5
1 2 3 1 2
6
8 7 8 9 7 4
7
2 3 4 5 6 7 8
8
8 1 2 7 7 9 6 10
9
6 11 4 5 8 9 11 3 4

stdout

1
-1
-1
4 7 8 9 7 8
8 2 3 4 5 6 7
10 9 1 8 6 7 2 7
11 3 11 6 9 4 5 4 8

Explanation

In the first test case, $b=[1]$ is a valid permutation of $a=[1]$, since:

• $b_1=1$, which is not divisible by $3$.

We can show that there are no solutions for the second and third test cases.

In the fourth test case, $b=[4,7,8,9,7,8]$ is a valid permutation of $a=[8,7,8,9,7,4]$, since:

• $b_1=4$, which is not divisible by $3$.
• $b_1+b_2=4+7=11$, which is not divisible by $3$.
• $b_1+b_2+b_3=4+7+8=19$, which is not divisible by $3$.
• $b_1+b_2+b_3+b_4=4+7+8+9=28$, which is not divisible by $3$.
• $b_1+b_2+b_3+b_4+b_5=4+7+8+9+7=35$, which is not divisible by $3$.
• $b_1+b_2+b_3+b_4+b_5+b_6=4+7+8+9+7+8=43$, which is not divisible by $3$.