P10830 [COTS 2023] Average Prosjek

Translated from [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) 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).

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.

**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.

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$.

#### 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}$. | Subtask ID | Score | Constraints | |:-----:|:------:|:-------:| | $1$ | $9$ | $T\le 100$, $N\le 7$ | | $2$ | $23$ | $T\le 100$, $a_i\le 10$ | | $3$ | $16$ | All $a_i$ are even | | $4$ | $52$ | No additional constraints | Translated by ChatGPT 5