After a training session, Piggy and his two teammates, along with their coach, went out for a meal. They chose a dim sum restaurant and ordered many dishes, such as shrimp dumplings, red rice rolls, and roast pigeon.

They ordered a total of $n$ dishes, where the $i$-th dish contains $a_i$ pieces of dim sum. To ensure an equal share, the total number of dim sum pieces is guaranteed to be a multiple of 4. However, due to the slow serving speed, and because the number of pieces in each dish is not necessarily a multiple of 4, the dim sum is often served in batches.

Whenever a dish is served, if the total number of dim sum pieces on the table is at least 4, the four people will each eat one piece until fewer than 4 pieces remain. Because the service is slow, the number of pieces on the table is always less than 4 before new dishes are served.

However, Piggy likes to sneakily eat! To avoid being discovered, Piggy will only quickly eat a piece if there is exactly 1 piece of dim sum left on the table. If Piggy eats it, everyone will mistakenly believe that the restaurant served an insufficient portion and will complain. As the manager of the restaurant, although you cannot speed up the service, you can adjust the order in which the dishes are served.

Now, please determine if there exists an order of serving the dishes such that Piggy has no opportunity to sneakily eat any dim sum, thereby avoiding customer complaints.

Input

The input contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^4$), representing the number of test cases.

For each test case: The first line contains an integer $n$ ($1 \le n \le 10^5$), representing the number of dishes. The next line contains $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le 100$). It is guaranteed that $\sum_{i=1}^n a_i$ is a multiple of 4, and the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case: If Piggy will sneakily eat a piece regardless of the order, output -1. Otherwise, output a permutation $p_1, \dots, p_n$, representing the order in which the dishes are served. The $i$-th dish served is the $p_i$-th dish from the input. If there are multiple solutions, any one of them is acceptable.

Examples

Input 1

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

Output 1

3 1 4 2
2 3 4 1
-1