Marco and GCD Sequence

题意翻译

### 题目大意 有一天$Macro$做梦梦见了一位戴着黑框眼睛的长者,那位长者告诉他长生不老的密匙, $Macro$还想继续追问,但那位长者只说了四个字"无可奉告".随即他就消失在时间之风中 Macro醒来后只记得密匙是一个长度为$N$的正整数序列$a_i$,但是他事先闷声发大财,计算了所有$gcd(a_i,a_{i+1}...a_j) (1<=i<=j<=n)$并且把结果放入单重集合$S$ 注意如果一个元素被多次放入集合,它只会出现一次 因为你比$Macro$不知道高到哪里去,现在$Macro$给你一个集合$S$，要求你还原出密匙序列。如果有多种解,输出任意一种.如果这个集合太$naive$,不可能还原出一个序列，那么输出"-1"(没有引号) ### 输入格式 第一行一个正整数$M(1<=M<=1000)$表示这个集合的大小 第二行按**升序**输出$M$个正整数$a_i(1<=a_i<=10^6)$表示集合中的元素 ### 输出格式 如果无解输出"-1"(没有引号) 否则第一行输出一个不超过$4000$的整数$N$表示密匙序列长度 第二行输入$N$个正整数$a_i (1<=a_i<=10^6)$表示序列元素 保证如果存在解,那么一定有一个解满足长度不会超过$4000$并且序列元素$a_i$不会超过$10^6$ 如果还是有多种解,输出任意一种

题目描述

In a dream Marco met an elderly man with a pair of black glasses. The man told him the key to immortality and then disappeared with the wind of time. When he woke up, he only remembered that the key was a sequence of positive integers of some length $ n $ , but forgot the exact sequence. Let the elements of the sequence be $ a_{1},a_{2},...,a_{n} $ . He remembered that he calculated $ gcd(a_{i},a_{i+1},...,a_{j}) $ for every $ 1<=i<=j<=n $ and put it into a set $ S $ . $ gcd $ here means the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor). Note that even if a number is put into the set $ S $ twice or more, it only appears once in the set. Now Marco gives you the set $ S $ and asks you to help him figure out the initial sequence. If there are many solutions, print any of them. It is also possible that there are no sequences that produce the set $ S $ , in this case print -1.

输入输出格式

输入格式

The first line contains a single integer $ m $ ( $ 1<=m<=1000 $ ) — the size of the set $ S $ . The second line contains $ m $ integers $ s_{1},s_{2},...,s_{m} $ ( $ 1<=s_{i}<=10^{6} $ ) — the elements of the set $ S $ . It's guaranteed that the elements of the set are given in strictly increasing order, that means $ s_{1}&lt;s_{2}&lt;...&lt;s_{m} $ .

输出格式

If there is no solution, print a single line containing -1. Otherwise, in the first line print a single integer $ n $ denoting the length of the sequence, $ n $ should not exceed $ 4000 $ . In the second line print $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{6} $ ) — the sequence. We can show that if a solution exists, then there is a solution with $ n $ not exceeding $ 4000 $ and $ a_{i} $ not exceeding $ 10^{6} $ . If there are multiple solutions, print any of them.

输入输出样例

输入样例 #1

4
2 4 6 12

输出样例 #1

3
4 6 12

输入样例 #2

2
2 3

输出样例 #2

-1

说明

In the first example $ 2=gcd(4,6) $ , the other elements from the set appear in the sequence, and we can show that there are no values different from $ 2 $ , $ 4 $ , $ 6 $ and $ 12 $ among $ gcd(a_{i},a_{i+1},...,a_{j}) $ for every $ 1<=i<=j<=n $ .