Loznica 是塞尔维亚的一座城市，以其历史、文化、宜人天气……以及彩票而闻名！Loznica 的彩票遵循以下规则：

• 彩票包含由 $N$ 个自然数组成的组合，所选数字均小于 $10^{18}$。
• 在这个彩票中，数字可以重复且顺序很重要。

Aljoha，我们故事的英雄，使用一些不为人知的工具，设法找到了下一张中奖彩票的一些信息。设未来的组合为 $L_{i}$，$1 \leq i \leq N$。Aloha 设法找到了一个包含 $N-1$ 个数字的数组，其中第 $i$ 个数字 $A_{i}$ 表示能同时整除 $L_{i}$ 和 $L_{i+1}$ 的最大数。

现在 Aljoha 想要下注，为了这个崇高的目标，他需要帮助。输出一个满足这些约束的组合，或者如果不存在这样的组合，则输出 $-1$。如果有多个满足约束的组合，输出其中任意一个。请注意，只有所有数字严格小于 $10^{18}$ 的组合才是有效的。

输入格式

第一行包含整数 $N$ ($1 \leq N \leq 10^5$)，表示组合的长度。

第二行包含 $N-1$ 个不超过 $10^9$ 的正整数，描述 Aljoha 得到的信息。

输出格式

输出 $N$ 个严格小于 $10^{18}$ 的数字，描述一个满足约束的组合；如果不存在这样的组合，则输出 $-1$。

示例

输入

4
3 4 10

输出

3 12 20 10

输入 2

4
3 4 6

输出 2

-1