There are $N$ non-negative integers written on a board. In one operation, you are allowed to choose any two numbers from the board whose sum is divisible by 2, remove the chosen numbers, and write a new number on the board - the arithmetic mean of the chosen numbers. Note that after each such operation, the new number on the board is also an integer.
Determine if it is possible to reach a situation where exactly one number remains on the board by performing a sequence of the described operations. Additionally, if it is possible, determine one such sequence of operations. You must determine the required operations for $T$ different situations, each with its own given board.
Input
The first line contains a natural number $T$, the number of different situations.
The following lines contain the descriptions of the situations in order. Each description is given in the following format:
The first line contains a natural number $N$.
The second line contains a sequence of non-negative integers $a_1, a_2, \dots, a_N$ representing the numbers written on the board. The given numbers are not necessarily distinct.
Output
For each situation, print the following:
If the required sequence of operations does not exist, print -1 in a single line.
Otherwise, in the $i$-th of the next $N - 1$ lines, print two non-negative integers $x_i$ and $y_i$ representing the choice of numbers on the board in the $i$-th operation. The chosen numbers must be present on the board at that moment, and their sum must be divisible by 2.
Subtasks
In all subtasks, $1 \le T \le 10^5$, $2 \le N \le 10^6$, and $0 \le a_i \le 10^{18}$ for all $i = 1, 2, \dots, N$. The sum of all values of $N$ over all situations is at most $10^6$.
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 9 | $T \le 100, N \le 7$ |
| 2 | 23 | $T \le 100, a_i \le 10$ for all $i = 1, 2, \dots, N$ |
| 3 | 16 | All numbers on all boards are even. |
| 4 | 52 | No additional constraints. |
Examples
Input 1
2 3 1 4 5 4 1 4 5 5
Output 1
-1 1 5 3 5 4 4
Input 2
1 6 1 2 3 4 5 6
Output 2
1 5 3 3 4 6 3 5 2 4
Note
Explanation of the second example:
The numbers on the board at the beginning are 1, 2, 3, 4, 5, and 6. The numbers on the board after the first operation are 2, 3, 4, 6, 3. The numbers on the board after the second operation are 2, 4, 6, 3. The numbers on the board after the third operation are 2, 3, 5. The numbers on the board after the fourth operation are 2, 4. The final number on the board is 3.