[AdditionalFile5525.zip](file://AdditionalFile5525.zip?type=additional_file)

#5525. 「COI 2025」Korupcija

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 COI 2025 T3「Korupcija」

“……腐败属于所有人，而不仅仅属于他们。我提供腐败、腐败的秩序、工作和增长。这些大师们向你们承诺的一切，我加倍提供。我还建议设立第八格：给谁？多少钱？……”

小米尔科被电视上那位叔叔的演讲迷住了。他深信自己理解了其中的信息：他必须「腐败」掉他二进制数的比特位。

米尔科观察着数字 $0, 1, \ldots, 2^{N}-1$（视为具有 $N$ 个二进制位的二进制数）。在腐败欲望的驱使下，米尔科会选择两个仅在一个比特位上不同的数字 $X$ 和 $Y$ $(0 \leq X, Y < 2^{N})$。然后，米尔科会用符号 $\texttt{?}$ 覆盖掉数字 $X$ 和 $Y$ 中那个不同的比特位，从而实现腐败：数字 $X$ 和 $Y$ 将变得无法区分。米尔科将对剩下的数字重复此过程，直到最终得到总共 $2^{N-1}$ 对无法区分的数字。因此，每个介于 $0$ 和 $2^{N}-1$ 之间的数字都恰好属于一个数对，并且两个数字能配成一对的唯一条件是它们恰好在一个比特位（二进制位）上不同。

为了增加挑战，米尔科决定，对于 $i=0, 1, \ldots, N-1$，他希望符号 $\texttt{?}$ 出现在第 $i$ 个比特位上的数对恰好有 $a_{i}$ 对。在这里，我们从最低有效位到最高有效位对比特位进行计数，因此第 $i$ 个比特位对应的值是 $2^{i}$。请帮助米尔科，构建一个满足所要求条件的配对方案，或者判断这样的方案不存在。

输入格式

第一行是一个自然数 $N$，来自题目描述。

第二行是一个包含 $N$ 个非负整数的序列 $a_{i}$，对于 $i=0, \ldots, N-1$，其中 $a_{i}$ 代表在第 $i$ 个比特位上不同的所要求数对数量。这些数字的总和恰好是 $2^{N-1}$。

输出格式

如果无法构建满足题目条件的配对方案，则在唯一的一行中输出 $-1$。

否则，输出 $2^{N-1}$ 行。每行输出两个用空格隔开的数字 $X$ 和 $Y$，代表一个选定的数对。你可以按任何顺序输出这些数对。

如果存在多种解，输出任意一种即可。

样例 1

输入

2
2 0

输出

0 1
2 3

样例 2

输入

2
1 1

输出

-1

样例 3

输入

3
2 0 2

输出

0 1
2 6
3 7
4 5

数据范围与提示

对于所有输入数据，满足 $1 \leq N \leq 20$。

在每个子任务中，$20\%$ 的分数仅来自于判断是否存在满足题目条件的配对方案。对于这部分分数，如果答案不为 $-1$，你需要输出某个配对方案，但它不必满足所要求的条件。