该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在黑板上写下了 $N$ 个非负整数。

在一次操作中，你可以选择黑板上任何两个整数，这两个整数的和可以被 $2$ 整除，然后擦掉这两个选中的数字，再在黑板上写下这两个选中数字的算术平均数。

请注意，每次这样的操作后，黑板上的新数字也是一个整数。

请确定是否有可能通过一系列上述的操作，使得黑板上只剩下一个数字。

此外，如果这是可能的，请给出一个可能的操作序列。

同样，你需要在 $T$ 个不同的情况下，确定需要的操作步骤，每个情况都有一个指定的黑板。

输入格式

首行是一个正整数 $T$，表示有 $T$ 个不同的情况。

接下来的行中，按顺序给出每个情况的描述。每个描述的格式如下：

首行是一个正整数 $N$。

第二行是一个非负整数序列 $a_1,a_2,\cdots,a_n$，代表黑板上写的数字。这些数字不一定是不同的。

输出格式

对于每种情况，请输出以下内容。

如果不存在所需的操作序列，在一行中输出 $-1$。

否则，对于接下来的 $N-1$ 行中的每一行 $i$，输出两个非负整数 $x_i$ 和 $y_i$，这两个数代表在第 $i$ 次操作中从黑板上选择的两个数。

选定的数必须在那个时刻在黑板上，且他们的和必须能被 $2$ 整除。

3
3
1 4 5
4
1 4 5 5
6
1 2 3 4 5 6

-1
1 5
3 5
4 4
1 5
3 3
4 6
3 5
2 4

样例解释 #1

对于第二组数据：

第一次操作 $x_1=1,y_1=5$，$(1+5)/2=3$，剩余 $3,4,5$。

第二次操作 $x_2=3,y_2=5$，$(3+5)/2=4$，剩余 $4,4$。

第三次操作 $x_3=4,y_3=4$，$(4+4)/2=4$，剩余 $4$。

样例输入/输出 #2

meow1.in
meow1.ans

样例输入/输出 #3

见选手目录下 $meow2.in/ans$，此样例符合子任务 $2$ 的限制。 meow2.in
meow2.ans

样例输入/输出 #4

见选手目录下 $meow3.in/ans$，此样例符合子任务 $3$ 的限制。 meow3.in
meow3.ans

样例输入/输出 #5

见选手目录下 $meow4.in/ans$，此样例符合子任务 $4$ 的限制。

meow4.in
meow4.ans

样例输入/输出 #6

见选手目录下 $meow5.in/ans$，此样例符合子任务 $5$ 的限制。

meow5.in
meow5.ans

数据范围与提示

在所有子任务中，$1 \le T \le 10^5$，$2 \le N \le 10^6$，$0 \le a_i \le 10^{18}$。

所有情况下 $N$ 的值的总和 $\le 10^6$

子任务 $1(9pts)$：$T \le 100,N \le 7$

子任务 $2(15pts)$：$T=1$，$a_i$ 在范围内均匀独立随机生成。

子任务 $3(23pts)$：$T \le 100,a_i \le 10$。

子任务 $4(16pts)$：$a_i$ 均为偶数。

子任务 $5(37pts)$：无特殊限制。