黑板上写着 $N$ 个非负整数。在一次操作中，允许选择黑板上的任意两个数，若它们的和能被 $2$ 整除，则将这两个数擦除，并在黑板上写下这两个数的算术平均值。注意，经过每次这样的操作后，黑板上的新数也一定是一个整数。

请确定是否可以通过一系列上述操作，使得黑板上最终恰好剩下一个数。如果可以，请给出一种实现该目标的操作序列。你需要针对 $T$ 种不同的情况分别求解，每种情况都有各自给定的黑板初始状态。

输入格式

第一行包含一个自然数 $T$，表示不同情况的数量。

接下来依次描述每种情况。每种情况的格式如下：

第一行包含一个自然数 $N$。

第二行包含 $N$ 个非负整数 $a_1, a_2, \dots, a_N$，表示写在黑板上的数。这些数不一定各不相同。

输出格式

对于每种情况，输出如下：

如果不存在满足要求的操作序列，则在唯一的一行中输出 -1。

否则，在接下来的 $N - 1$ 行中，每行输出两个非负整数 $x_i$ 和 $y_i$，表示第 $i$ 次操作中选择的两个数。所选的数必须在当前时刻存在于黑板上，且它们的和必须能被 $2$ 整除。

子任务

在所有子任务中，满足 $1 \le T \le 10^5$，$2 \le N \le 10^6$，且对于所有 $i = 1, 2, \dots, N$ 有 $0 \le a_i \le 10^{18}$。所有情况下的 $N$ 之和不超过 $10^6$。

样例

样例输入 1

2
3
1 4 5
4
1 4 5 5

样例输出 1

-1
1 5
3 5
4 4

样例输入 2

1
6
1 2 3 4 5 6

样例输出 2

1 5
3 3
4 6
3 5
2 4

说明

第二个样例的解释： 初始黑板上的数为 1, 2, 3, 4, 5, 6。 第一次操作后的数为 2, 3, 4, 6, 3。 第二次操作后的数为 2, 4, 6, 3。 第三次操作后的数为 2, 3, 5。 第四次操作后的数为 2, 4。 最终黑板上的数为 3。