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.

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.


-----Input-----

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 < s_2 < ... < s_{m}.


-----Output-----

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.


-----Examples-----
Input
4
2 4 6 12

Output
3
4 6 12
Input
2
2 3

Output
-1



-----Note-----

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.

Difficulty: HARD
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
from math import gcd
m = int(input())
s = sorted(list(map(int, input().split())))
a = 0
for e in s:
	a = gcd(a, e)
if a != s[0]:
	print(-1)
else:
	print(2 * m - 1)
	v = [0] * (2 * m - 1)
	for i in range(2 * m - 1):
		if i % 2 == 0:
			v[i] = s[i // 2]
		else:
			v[i] = a
	print(*v)


from collections import defaultdict as dd
from collections import Counter as ccd
from itertools import permutations as pp
from itertools import combinations as cc
from random import randint as rd
from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq as hq
import math
mod = pow(10, 9) + 7

def inp(flag=0):
	if flag == 0:
		return list(map(int, input().strip().split(' ')))
	else:
		return int(input())
n = int(input())
s = inp()
ans = []
possible = True
for i in range(n):
	if s[i] % s[0] != 0:
		possible = False
		break
	ans.append(s[0])
	ans.append(s[i])
if possible:
	print(2 * n)
	print(*ans)
else:
	print(-1)


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
n = int(input())
a = input().split(' ')
t = 0
for i in a:
	t = gcd(t, int(i))
if t != int(a[0]):
	print(-1)
else:
	print(2 * a.__len__())
	for i in a:
		print('%d %d' % (int(i), t), end=' ')


def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if a == b:
		return a
	if b == 0:
		return a
	return gcd(a % b, b)

def gcd_group(a, s):
	if s == 1:
		return a[0]
	if s == 2:
		return gcd(a[0], a[1])
	return gcd(gcd_group(a[:-1], s - 1), a[-1])
m = int(input())
a = list(map(int, input().split()))
if m == 1:
	print(1)
	print(a[0])
else:
	t = 0
	for i in a[1:]:
		if i % a[0] != 0:
			print(-1)
			t = 1
			break
	if t == 0:
		k = [str(a[0])]
		for i in a[1:]:
			k.append(str(i))
			k.append(str(a[0]))
		print(2 * m - 1)
		print(' '.join(k))


n = int(input())
ls = list(map(int, input().split()))
for i in range(n):
	if ls[i] % ls[0] != 0:
		print(-1)
		exit()
print(n * 2)
for i in range(n):
	print(ls[0], ls[i], end=' ')


n = int(input())
A = [int(i) for i in input().split(' ')]
mi = min(A)
ok = 1
for i in A:
	if i % mi:
		print(-1)
		ok = 0
		break
if ok:
	print(2 * n - 1)
	print(A[0], end=' ')
	for i in range(1, n):
		print(mi, A[i], end=' ')


import math
R = lambda : map(int, input().split())
n = R()
a = [i for i in R()]
d = a[0]
w = [a[0], a[0]]
for i in range(1, len(a)):
	d = math.gcd(d, a[i])
	w.extend((a[i], a[0]))
if d != min(a):
	(print(-1), exit())
print(len(w) - 1)
for i in w[:-1]:
	print(i, end=' ')


n = int(input())
l = [int(i) for i in input().split()]

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
g = 0
for i in l:
	g = gcd(g, i)
if g != min(l):
	print(-1)
else:
	print(2 * n - 1)
	print(l[0], end=' ')
	for i in range(1, n):
		print(min(l), l[i], end=' ')


import math
n = int(input())
x = [int(k) for k in input().split(' ')]
m = x[0]
chk = [max(0, x[i] % m) for i in range(n)]
if sum(chk) > 0:
	print(-1)
else:
	print(2 * n - 1)
	o = []
	o.append(str(m))
	for i in range(1, n):
		o.append(str(x[i]))
		o.append(str(m))
	print(' '.join(o))


import os, sys
from io import BytesIO, IOBase
from math import gcd

def main():
	m = int(input())
	s = list(map(int, input().split()))
	for i in range(1, m):
		if gcd(s[i], s[0]) != s[0]:
			print(-1)
			exit()
	print(2 * m)
	for i in s:
		print(i, s[0], end=' ')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
s = input().split()
i = list(map(int, s))
if all(map(lambda x: x % i[0] == 0, i)):
	ans = str(2 * n - 1) + '\n'
	ans += (' ' + s[0] + ' ').join(s)
else:
	ans = -1
print(ans)


import sys

def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while b != 0:
		temp = a % b
		a = b
		b = temp
	return a
n = int(input())
a = [i for i in map(int, input().split())]
a.sort()
s = True
for i in range(n):
	if a[i] % a[0] != 0:
		s = False
if s:
	print(2 * n)
	for i in range(n):
		print(a[0], a[i], end=' ')
else:
	print(-1)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def solve(a):
	if len(a) == 1:
		return (1, str(a[0]))
	d = {x: 1 for x in a}
	arr = []
	g_ = a[0]
	for x in a[1:]:
		g_ = gcd(g_, x)
	if g_ not in d:
		return (-1, None)
	return (2 * len(a) - 1, ' {} '.format(str(g_)).join([str(x) for x in a]))
n = int(input())
a = list(map(int, input().split()))
arr = solve(a)
if arr[0] == -1:
	print(-1)
else:
	print(arr[0])
	print(arr[1])


n = int(input())
a = list(map(int, input().split()))
cur = a[-1]
from math import gcd
for i in range(1, n - 1):
	cur = gcd(cur, a[i])
if cur % a[0] != 0 and a[0] != 1:
	print(-1)
else:
	print(2 * n)
	for i in a:
		print(i, a[0], end=' ')


def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while b != 0:
		(a, b) = (b, a % b)
	return a

def gcd_set(nums):
	a = nums[0]
	for b in nums[1:]:
		a = gcd(a, b)
	return a

def solution(seq):
	seq = list(reversed(seq))
	seq_set = set(seq)
	root = gcd_set(seq)
	if root not in seq_set:
		print(-1)
		return
	answer = []
	for (i, s) in enumerate(seq):
		answer.append(s)
		answer.append(root)
		for p in seq[i + 1:]:
			g = gcd(s, p)
	print(len(answer))
	print(' '.join(map(str, answer)))
input()
seq = list(map(int, input().split()))
solution(seq)


import sys
input = sys.stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())

class Div2_447_C:

	def __init__(self):
		self.m = I()
		self.s = L()
		self.ans = []

	def solve(self):
		g = self.s[0]
		for x in self.s:
			if x % g:
				print(-1)
				return
			self.ans += [x, g]
		print(len(self.ans))
		print(*self.ans)
		return
obj = Div2_447_C()
obj.solve()


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
s = list(map(int, input().split()))
g = 0
for i in range(0, n):
	g = gcd(g, s[i])
if g != s[0]:
	print('-1')
else:
	ans = ''
	print(2 * n - 1)
	for i in range(1, n):
		ans += str(s[0]) + ' '
		ans += str(s[i]) + ' '
	ans += str(s[0])
	print(ans)


from math import gcd
m = int(input())
s = [int(i) for i in input().split()]
gc = s[0]
for i in range(0, m):
	gc = gcd(gc, s[i])
if gc not in s:
	print(-1)
else:
	print(2 * m - 1)
	ans = [s[0]] * (2 * m - 1)
	cur = 1
	for i in range(2, 2 * m - 1, 2):
		ans[i] = s[cur]
		cur += 1
	print(*ans)


from fractions import gcd
n = int(input())
l = input()
l = [int(i) for i in l.split()]
s = set()
r = []
f = l[0]
for i in range(1, len(l)):
	f = gcd(f, l[i])
if f != l[0]:
	print(-1)
else:
	print(2 * n)
	for i in range(n):
		print(l[0], end=' ')
		print(l[i], end=' ')


from math import gcd
n = int(input())
l = [int(x) for x in input().split()]
for i in range(n):
	if l[i] % l[0]:
		print('-1')
		exit(0)
print(2 * n)
for i in range(n):
	print(l[0], l[i], end=' ')


def main():
	m = int(input())
	a = list(map(int, input().split()))
	for i in range(1, m):
		if a[i] % a[0] != 0:
			print(-1)
			exit()
	print(2 * m - 1)
	print(a[0], end=' ')
	for i in range(1, m):
		print(a[i], a[0], end=' ')
main()


from collections import defaultdict, deque
import sys
import bisect
input = sys.stdin.readline
n = int(input())
hcf = [int(i) for i in input().split() if i != '\n']
ans = []
if n == 1:
	print(1)
	print(hcf[0])
else:
	for i in range(1, n):
		if hcf[i] % hcf[0] != 0:
			print(-1)
			break
	else:
		for i in range(n):
			ans.append(hcf[i])
			ans.append(hcf[0])
		print(len(ans))
		print(*ans)


n = int(input())
k = [int(x) for x in input().split()]
m = min(k)
FL = 1
for i in k:
	if i % m:
		print(-1)
		FL = 0
		break
if FL:
	print(n * 2)
	for i in k:
		print(m, i, end=' ')


m = int(input())
set = list(map(int, input().split()))
flag = True
if m == 1:
	print(1)
	print(set[0])
	flag = False
for s in set:
	if s % set[0] != 0:
		print(-1)
		flag = False
		break
if flag:
	list = []
	for i in set[1:]:
		list.append(set[0])
		list.append(i)
	print(len(list))
	for (i, n) in enumerate(list):
		if i != len(list) - 1:
			print(n, end=' ')
		else:
			print(n)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(200001)]
pp = [0] * 200001

def SieveOfEratosthenes(n=200000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
n = int(input())
l = list(map(int, input().split()))
if n == 1:
	print(n)
	print(*l)
	sys.exit(0)
l.sort()
for i in range(1, n):
	if l[i] % l[0] != 0:
		print(-1)
		sys.exit(0)
t = 1
ans = []
for i in range(2 * (n - 1)):
	if i % 2 == 0:
		ans.append(l[0])
	else:
		ans.append(l[t])
		t += 1
print(len(ans))
print(*ans)


m = int(input())
A = input().split()
A = [int(i) for i in A]
final = []
for i in range(1, m):
	if A[i] % A[0] != 0:
		print(-1)
		break
	else:
		final = final + [A[i]] + [A[0]]
final = [str(i) for i in final]
if m == 1:
	print(1)
	print(A[0])
elif len(final) == 2 * (m - 1):
	print(2 * (m - 1))
	for i in final:
		print(i, end=' ')


from math import gcd

def gcda(a):
	r = a[0]
	for e in a:
		r = gcd(r, e)
	return r
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
if gcda(a) != a[0]:
	print(-1)
else:
	print(n * 2)
	for e in a:
		print(e, end=' ')
		print(a[0], end=' ')


m = int(input())
S = list(map(int, input().split()))
if S[0] != 1:
	for i in range(1, m):
		if S[i] % S[0]:
			print(-1)
			exit(0)
SS = []
for i in range(m):
	SS.append(S[0])
	SS.append(S[i])
SS.append(S[0])
print(len(SS))
print(*SS)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
(mn, res) = (min(a), [])
for i in a:
	if gcd(mn, i) == mn:
		res.append(mn)
		res.append(i)
	else:
		print(-1)
		exit()
print(len(res))
print(*res)


n = int(input())
a = list(map(int, input().split()))
a.sort()
i = 0
flag = True
for i in range(1, n):
	if a[i] % a[0] != 0:
		flag = False
		break
if not flag:
	print(-1)
elif n == 1:
	print(1)
	print(a[0])
else:
	print(2 * n - 2)
	for i in range(1, n):
		print(str(a[0]) + ' ' + str(a[i]), end=' ')
	print()


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
v = list(map(int, input().split()))
g = v[0]
for i in range(1, n, 1):
	g = gcd(g, v[i])
has = 0
for i in range(n):
	if v[i] == g:
		has = 1
if has == 0:
	print('-1')
else:
	print('%d' % int(2 * n))
	for i in range(n):
		print('%d %d ' % (int(v[i]), int(g)), end='')
	print('')


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=300006, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.height = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val == 0:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
			elif val >= 1:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left

	def do(self, temp):
		if not temp:
			return 0
		ter = temp
		temp.height = self.do(ter.left) + self.do(ter.right)
		if temp.height == 0:
			temp.height += 1
		return temp.height

	def query(self, xor):
		self.temp = self.root
		cur = 0
		i = 31
		while i > -1:
			val = xor & 1 << i
			if not self.temp:
				return cur
			if val >= 1:
				self.opp = self.temp.right
				if self.temp.left:
					self.temp = self.temp.left
				else:
					return cur
			else:
				self.opp = self.temp.left
				if self.temp.right:
					self.temp = self.temp.right
				else:
					return cur
			if self.temp.height == pow(2, i):
				cur += 1 << i
				self.temp = self.opp
			i -= 1
		return cur
n = int(input())
l = list(map(int, input().split()))
if n == 1:
	print(n)
	print(*l)
	sys.exit(0)
l.sort()
for i in range(1, n):
	if l[i] % l[0] != 0:
		print(-1)
		sys.exit(0)
t = 1
ans = []
for i in range(2 * (n - 1)):
	if i % 2 == 0:
		ans.append(l[0])
	else:
		ans.append(l[t])
		t += 1
print(len(ans))
print(*ans)


def gcd(a, b):
	while b > 0:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)
n = int(input())
lst = list(map(int, input().split()))
res = lst.copy()
tmp = 0
for i in range(1, n):
	if lst[i] % lst[0] != 0:
		print(-1)
		exit()
print(len(res) * 2)
for i in range(n):
	print(lst[0], lst[i], end=' ')


from functools import reduce
n = int(input())
arr = list(map(int, input().split()))

def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	if b % a == 0:
		return a
	return gcd(a, b % a)
g = reduce(gcd, arr)
if g != min(arr):
	print(-1)
else:
	ans = []
	for elt in arr:
		ans.append(g)
		ans.append(elt)
	print(len(ans))
	print(' '.join(list(map(str, ans))))


def main():
	m = int(input())
	l = list(map(int, input().split())) * 2
	a = l[0]
	for i in range(m - 1, 0, -1):
		b = l[i]
		if b % a:
			print(-1)
			return
		l[i * 2] = b
		l[i * 2 - 1] = a
	print(m * 2)
	print(*l)
main()


length = int(input())
number = list(map(int, input().split()))
lis = []
flag = 0
for i in range(length):
	if number[i] % number[0] == 0:
		lis.append(number[0])
		lis.append(number[i])
	else:
		print(-1)
		flag = 1
		break
if flag == 0:
	print(len(lis))
	print(*lis)


m = int(input())
a = list(map(int, input().split()))

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
cur = min(a)
for i in range(1, m):
	if a[i] % cur != 0:
		print('-1')
		exit(0)
L = [cur]
for i in range(m):
	if a[i] != cur:
		L.append(a[i])
		L.append(cur)
print(len(L))
for i in range(len(L)):
	print(L[i], end=' ')


n = int(input())
s = list(map(int, input().split()))
p = s[0]
for i in s:
	if i % p:
		print(-1)
		exit(0)
ans = []
for i in s:
	ans += [i, p]
print(len(ans))
print(*ans)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
N = int(input())
A = [int(x) for x in input().split()]

def gcd(x, y):
	if x < y:
		return gcd(y, x)
	if y == 0:
		return x
	return gcd(y, x % y)
x = A[0]
for v in A[1:]:
	x = gcd(x, v)
if A[0] != x:
	print(-1)
else:
	print(2 * len(A) - 1)
	print((' %d ' % A[0]).join(map(str, A)))


n = int(input())
a = list(map(int, input().split()))
for i in a:
	if i % a[0]:
		print(-1)
		break
else:
	print(2 * n, '\n', *map(lambda i: f'{a[i]} {a[0]}', range(n)))


n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	if a[n - 1 - i] % a[0] != 0:
		print(-1)
		exit(0)
print(2 * n)
for i in range(n):
	print(a[0], ' ', a[i], ' ')


from sys import *

def gcd(a, b):
	if not a:
		return b
	return gcd(b % a, a)
n = int(input())
a = list(map(int, input().split()))
if n == 1:
	print(2)
	print(a[0], a[0])
	exit(0)
g = gcd(a[0], a[1])
for i in range(2, n):
	g = gcd(g, a[i])
if g in a:
	print(2 * n)
	for i in range(n):
		print(a[i], g, end=' ')
else:
	print(-1)


from math import gcd
m = int(input())
s = list(map(int, input().split()))
if m <= 1:
	print('1')
	print(s[0])
	exit()
d = s[0]
for i in range(1, m):
	d = gcd(d, s[i])
if d != s[0]:
	print(-1)
else:
	print(2 * m)
	ans = []
	for i in range(m):
		ans.append(s[i])
		ans.append(s[0])
	print(' '.join(map(str, ans)))


def gcd(a: int, b: int):
	while b:
		(a, b) = (b, a % b)
	return a
m = int(input())
s = list(map(int, input().split()))
se = set(s)
ans = [s[0]]
ok = True
for i in range(1):
	g = s[i]
	for j in range(i + 1, m):
		g = gcd(g, s[j])
		if g not in se:
			ok = False
			break
		ans.append(s[j])
		ans.append(s[0])
if not ok:
	print(-1)
	exit()
print(len(ans))
print(*ans)


def gcd(a, b):
	if a % b == 0:
		return b
	return gcd(b, a % b)
n = int(input())
a = [int(i) for i in input().split()]
s = a[0]
for i in a:
	s = gcd(s, i)
if s == a[0]:
	print(3 * n)
	for i in a:
		print(s, i, s, end=' ')
else:
	print(-1)


from sys import stdin
n = int(stdin.readline())
s = [int(x) for x in stdin.readline().split()]

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
s = set(s)
flag2 = False
for x in s:
	flag = True
	for y in s:
		if not gcd(x, y) in s:
			flag = False
			break
	if flag:
		flag2 = x
		break
if flag2 != False:
	print(n * 2)
	for x in s:
		print(x, flag2, end=' ')
else:
	print(-1)


def gcd(a, b):
	while b > 0:
		r = a % b
		a = b
		b = r
	return a
inp = lambda : map(int, input().split())
m = int(input())
a = list(inp())
g = a[0]
for i in range(1, m):
	g = gcd(g, a[i])
if g != a[0]:
	print('-1')
	quit()
print(2 * m - 1)
print(a[0], '', end='')
for i in range(1, m):
	print(a[i], a[0], '', end='')


from fractions import gcd
from functools import reduce
m = int(input())
a = list(map(int, input().split()))
ans = []
if reduce(gcd, a) == a[0]:
	for i in range(1, m):
		ans.append(a[0])
		ans.append(a[i])
	ans.append(a[0])
	print(len(ans))
	print(' '.join(map(str, ans)))
else:
	print(-1)


from fractions import gcd
n = int(input())
a = [int(z) for z in input().split()]
g = 0
for i in range(n):
	g = gcd(g, a[i])
if a[0] != g:
	print(-1)
	exit(0)
print(2 * n)
for i in range(n):
	print(g, a[i], end=' ')


import sys, queue, string, math, itertools
try:
	import dev_act_ffc429465ab634
	DEV = True
except:
	DEV = False

def log(*s):
	if DEV:
		print('LOG', *s)

class EJudge:

	def __init__(self, problem='default', reclim=1 << 30):
		self.problem = problem
		sys.setrecursionlimit(reclim)

	def use_files(self, infile='', outfile=''):
		if infile != '':
			self.infile = open(infile)
			sys.stdin = self.infile
		if infile != '':
			self.outfile = open(outfile, 'w')
			sys.stdout = self.outfile

	def use_bacs_files(self):
		self.use_files(self.problem + '.in', self.problem + '.out')

	def get_tl(self):
		while True:
			pass

	def get_ml(self):
		tmp = [[[5] * 100000 for _ in range(1000)]]
		while True:
			tmp.append([[5] * 100000 for _ in range(1000)])

	def get_re(self):
		s = (0,)[8]

	def get_wa(self, wstr='blablalblah'):
		for _ in range(3):
			print(wstr)
		exit()

class IntReader:

	def __init__(self):
		self.ost = queue.Queue()

	def get(self):
		return int(self.sget())

	def sget(self):
		if self.ost.empty():
			for el in input().split():
				self.ost.put(el)
		return self.ost.get()

	def release(self):
		res = []
		while not self.ost.empty():
			res.append(self.ost.get())
		return res
ej = EJudge('')
int_reader = IntReader()
fmap = lambda f, *l: list(map(f, *l))
parse_int = lambda : fmap(int, input().split())
revrange = lambda x: range(x - 1, -1, -1)
n = int(input())
a = parse_int()
mgcd = a[0]
for el in a[1:]:
	if el % mgcd != 0:
		print(-1)
		exit()
print(2 * len(a))
print(' '.join(fmap(lambda x: str(mgcd) + ' ' + str(x), a)))


m = int(input())
s = list(map(int, input().split(' ')))
fl = True
for i in range(1, m):
	if s[i] % s[0]:
		fl = False
		break
if not fl:
	print(-1)
else:
	print(m * 2)
	for i in range(m):
		print(s[i], s[0], end=' ')


m = int(input())
s = list(map(int, input().split()))
f = 1
for i in s:
	if i % s[0] != 0:
		f = 0
		break
if f:
	print(2 * m)
	for i in s:
		print(str(s[0]) + ' ' + str(i), end=' ')
else:
	print(-1)


import sys
n = int(input())
a = list(map(int, input().split()))
for i in range(1, n):
	if a[i] % a[0]:
		print(-1)
		sys.exit(0)
print(2 * n)
for x in a:
	print(str(x) + ' ' + str(a[0]), end=' ')


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
a = list(map(int, input().split()))
gcd1 = a[0]
for i in range(1, n):
	gcd1 = gcd(gcd1, a[i])
if gcd1 not in a:
	print(-1)
else:
	s = ''
	for i in range(n):
		s += str(gcd1) + ' ' + str(a[i]) + ' ' + str(gcd1) + ' '
	print(3 * n)
	print(s[:-1])