C. Марко и НОД-последовательность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во сне Марко встретил пожилого мужчину в темных очках. Мужчина сообщил ему ключ к бессмертию и затем исчез.

Когда он проснулся, Марко помнил только то, что ключ был последовательностью целых чисел некоторой длиной n, но забыл саму последовательность. Пусть элементы последовательности были a1, a2, ..., an. Марко помнит, что он сосчитал gcd(ai, ai + 1, ..., aj) для всех 1 ≤ i ≤ j ≤ n и сложил эти числа в множество S. Здесь gcd обозначает наибольший общий делитель.

Обратите внимание, если число добавляется во множество S больше одного раза, оно все равно будет там встречаться только один раз.

Марко дал вам множество 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.

Если решений несколько, выведите любое.

Примеры
Входные данные
4
2 4 6 12
Выходные данные
3
4 6 12
Входные данные
2
2 3
Выходные данные
-1
Примечание

В первом примере 2 = gcd(4, 6), а остальные элементы из множества встречаются в последовательности. Кроме того, можно показать, что нет чисел, отличных от 2, 4, 6 и 12 среди всех gcd(ai, ai + 1, ..., aj) для всех 1 ≤ i ≤ j ≤ n.