在梦中,马可遇到了一位戴着黑色眼镜的老人。那人告诉了他长生不老的钥匙,然后就随着时间之风消失了。
当他醒来时,他只记得密钥是一个长度为n的正整数序列,但忘记了确切的序列。令序列的元素为a1,a2,...,an。他记得他对每一个 1 ≤ i ≤ j ≤ n 计算了 gcd(ai, ai + 1, ..., aj) 并将其放入集合 S 中。这里的 gcd 是指最大公约数。
注意,即使一个数字被放入集合S中两次或更多次,它也只会在集合中出现一次。
现在Marco给你集合S并要求你帮助他找出初始序列。如果有很多解决方案,请打印其中任何一个。也有可能没有序列产生集合 S,在这种情况下打印 -1。
输入
第一行包含一个整数 m (1 ≤ m ≤ 1000) — 集合 S 的大小。
第二行包含 m 个整数 s1, s2, ..., sm (1 ≤ si ≤ 106) — 集合 S 的元素。保证集合的元素严格按递增顺序给出,即 s1 < s2 < ... < sm。
输出
如果没有解决方案,则打印包含 -1 的单行。
否则,在第一行打印一个整数 n 表示序列的长度,n 不应超过 4000。
在第二行中打印 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 106) - 序列。
我们可以证明,如果存在解,则存在n不超过4000且ai不超过106的解。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
4 2 4 6 12
输出 #1
3 4 6 12
输入 #2
2 2 3
输出 #2
-1
注意
在第一个示例 2 = gcd(4, 6) 中,集合中的其他元素出现在序列中,我们可以证明,对于每个 1 ≤ i ≤ j ≤ n,gcd(ai, ai + 1, ..., aj) 中不存在与 2、4、6 和 12 不同的值。