Cody the Wolf 是一支程序设计竞赛队伍的教练。随着新赛季的临近，Cody 打算招募一些新成员加入队伍。他为这次招募准备了一道编程题：

• 有一个包含 $n$ 个正整数和 $n-1$ 个加号的表达式 $a_1 + a_2 + \dots + a_n$。我们每次将一个加号 $+$ 替换为乘号 $\times$，总共进行 $n-1$ 次替换。请计算每次替换后表达式的结果。

Cody 已经生成了这道题的标准输入和输出文件。但他不小心删除了所有的标准输入文件。Cody 非常苦恼，他想知道在保持输出文件不变的情况下，是否能恢复对应的输入文件。

形式化地，给定 $n$ 个整数 $s_0, s_1, \dots, s_{n-1}$，其中 $s_i$ 表示第 $i$ 次替换后表达式的结果，你需要构造一个初始表达式 $a_1 + a_2 + \dots + a_n$，并确定每次替换时所选加号的位置，使得每次替换后的结果与给定的整数 $s_0, s_1, \dots, s_{n-1}$ 相匹配。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示表达式中整数的个数。 第二行包含 $n$ 个整数 $s_0, s_1, \dots, s_{n-1}$ ($1 \le s_i \le 10^9$)，其中 $s_i$ 表示第 $i$ 次替换后表达式的结果。

输出格式

如果不存在可能的解，输出 $-1$。 否则，在第一行输出 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示初始表达式为 $a_1 + a_2 + \dots + a_n$。接着输出 $n-1$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次替换时所选加号的位置。你需要使这 $n-1$ 个整数构成 $1$ 到 $n-1$ 的一个排列，即 $1$ 到 $n-1$ 中的每个整数恰好出现一次。 如果存在多种解，输出任意一种即可。

样例

输入格式 1

4
13 12 19 60

输出格式 1

5 3 4 1
3
1
2

说明

• 第 0 次替换后的表达式，即初始表达式为 $5 + 3 + 4 + 1 = 13$。
• 第 1 次替换后的表达式为 $5 + 3 + 4 \times 1 = 12$。
• 第 2 次替换后的表达式为 $5 \times 3 + 4 \times 1 = 19$。
• 第 3 次替换后的表达式为 $5 \times 3 \times 4 \times 1 = 60$。

输入格式 2

10
10 9 8 7 6 5 4 3 2 1

输出格式 2

1 1 1 1 1 1 1 1 1 1
1
2
3
4
5
6
7
8
9

输入格式 3

6
1 1 4 5 1 4

输出格式 3

-1