Background

Translated from Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection) D1T2. $\texttt{3s,0.5G}$.

Happy birthday to NaCly_Fish! (2024.7.28).

Thanks to @Rainbow_qwq for fixing the interactive library. A warning to future readers: use multiset.count with caution (its complexity may degrade to linear).

Problem Description

There are $N$ non-negative integers on a blackboard. In one operation, you may choose two integers $a, b$ on the blackboard such that $2\mid (a+b)$, erase $a, b$ from the blackboard, and then write down $(a+b)/2$. Note that after each operation, all numbers on the blackboard are still integers.

Determine whether it is possible to make only one number remain on the blackboard. If it is possible, you also need to provide one sequence of operations.

Input Format

This problem contains multiple test cases in a single test file.

The first line contains a positive integer $T$, the number of test cases.

The following describes $T$ test cases.

For each test case, the first line contains a positive integer $N$, the number of integers on the blackboard.

The second line contains $N$ non-negative integers, describing the numbers on the blackboard.

Output Format

For each test case, output several lines.

If it is impossible, output one line with $\texttt{-1}$.

Otherwise, output $(N-1)$ lines, each containing two integers, representing the two numbers to erase in each operation. You must ensure that the chosen numbers exist, and that their sum is divisible by $2$.

2
3
1 4 5
4
1 4 5 5

-1
1 5
3 5
4 4

1
6
1 2 3 4 5 6

1 5
3 3
4 6
3 5
2 4

Hint

Sample Explanation

Explanation for sample $2$: $[\boldsymbol{\textcolor{red}{1}},2,3,4,\boldsymbol{\textcolor{red}{5}},6] \to [\boldsymbol{\textcolor{red}{3}},2,\boldsymbol{\textcolor{red}{3}},4,6]\to [3,2,\boldsymbol{\textcolor{red}{4}},\boldsymbol{\textcolor{red}{6}}]\to [\boldsymbol{\textcolor{red}{5}},\boldsymbol{\textcolor{red}{3}},2]\to [\boldsymbol{\textcolor{red}{4}},\boldsymbol{\textcolor{red}{2}}]\to [3]$.

Constraints

For $100\%$ of the data, it is guaranteed that:

• $1\le T\le 10^5$;
• $1\le N,\sum N\le 10^6$;
• $0\le a_i\le 10^{18}$.

Translated by ChatGPT 5