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*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. He remembered that he calculated *gcd*(*a*<sub class="lower-index">*i*</sub>, *a*<sub class="lower-index">*i* + 1</sub>, ..., *a*<sub class="lower-index">*j*</sub>) 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*<sub class="lower-index">1</sub>, *s*<sub class="lower-index">2</sub>, ..., *s*<sub class="lower-index">*m*</sub> (1 ≤ *s*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>) — the elements of the set *S*. It's guaranteed that the elements of the set are given in strictly increasing order, that means *s*<sub class="lower-index">1</sub> &lt; *s*<sub class="lower-index">2</sub> &lt; ... &lt; *s*<sub class="lower-index">*m*</sub>.
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*<sub class="lower-index">*i*</sub>, *a*<sub class="lower-index">*i* + 1</sub>, ..., *a*<sub class="lower-index">*j*</sub>) for every 1 ≤ *i* ≤ *j* ≤ *n*.
4
2 4 6 12
7
2 2 4 2 6 2 12
2
2 3
-1
2
1 6
3
1 1 6
3
1 2 7
5
1 1 2 1 7
1
1
1
1
2
1 10
3
1 1 10
3
1 2 6
5
1 1 2 1 6
15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
29
1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15
14
1 2 3 4 5 6 7 8 9 10 11 12 13 14
27
1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14
5
2 5 6 7 11
-1
11
3 4 5 6 7 8 9 10 11 12 13
-1
3
4 9 11
-1
6
5 6 9 11 14 16
-1
12
8 9 10 11 12 13 14 15 16 17 18 19
-1
3
1007 397765 414884
5
1007 1007 397765 1007 414884
19
1007 27189 32224 47329 93651 172197 175218 234631 289009 340366 407835 468255 521626 579025 601179 605207 614270 663613 720005
37
1007 1007 27189 1007 32224 1007 47329 1007 93651 1007 172197 1007 175218 1007 234631 1007 289009 1007 340366 1007 407835 1007 468255 1007 521626 1007 579025 1007 601179 1007 605207 1007 614270 1007 663613 1007 720005
36
1007 27189 42294 81567 108756 133931 149036 161120 200393 231610 234631 270883 302100 307135 343387 344394 362520 383667 421933 463220 486381 526661 546801 571976 595137 615277 616284 629375 661599 674690 680732 714970 744173 785460 787474 823726
71
1007 1007 27189 1007 42294 1007 81567 1007 108756 1007 133931 1007 149036 1007 161120 1007 200393 1007 231610 1007 234631 1007 270883 1007 302100 1007 307135 1007 343387 1007 344394 1007 362520 1007 383667 1007 421933 1007 463220 1007 486381 1007 526661 1007 546801 1007 571976 1007 595137 1007 615277 1007 616284 1007 629375 1007 661599 1007 674690 1007 680732 1007 714970 1007 744173 1007 785460 1007 787474 1007 823726
49
1007 24168 33231 34238 51357 68476 75525 89623 99693 128896 149036 150043 162127 178239 184281 203414 216505 224561 232617 260813 274911 300086 325261 337345 365541 367555 378632 384674 405821 407835 419919 432003 460199 466241 492423 515584 531696 549822 572983 589095 616284 624340 653543 683753 700872 704900 713963 736117 737124
97
1007 1007 24168 1007 33231 1007 34238 1007 51357 1007 68476 1007 75525 1007 89623 1007 99693 1007 128896 1007 149036 1007 150043 1007 162127 1007 178239 1007 184281 1007 203414 1007 216505 1007 224561 1007 232617 1007 260813 1007 274911 1007 300086 1007 325261 1007 337345 1007 365541 1007 367555 1007 378632 1007 384674 1007 405821 1007 407835 1007 419919 1007 432003 1007 460199 1007 466241 1007 492423 1007 515584 1007 531696 1007 549822 1007 572983 1007 589095 1007 616284 1007 624340 1007 653543 1007 6...
3
99997 599982 999970
5
99997 99997 599982 99997 999970
2
99997 399988
3
99997 99997 399988
4
99997 399988 499985 599982
7
99997 99997 399988 99997 499985 99997 599982
4
19997 339949 539919 719892
7
19997 19997 339949 19997 539919 19997 719892
2
299997 599994
3
299997 299997 599994
1
999997
1
999997
1
1000000
1
1000000
2
999999 1000000
-1
2
999996 1000000
-1
3
250000 750000 1000000
5
250000 250000 750000 250000 1000000
2
666666 999999
-1
4
111111 666666 777777 999999
7
111111 111111 666666 111111 777777 111111 999999
5
111111 233333 666666 777777 999999
-1
6
111111 222222 333333 666666 777777 999999
11
111111 111111 222222 111111 333333 111111 666666 111111 777777 111111 999999
2
1 2
3
1 1 2
1
233333
1
233333
from bisect import *
from collections import *
import sys
import io, os
import math
import random
from heapq import *
gcd = math.gcd
sqrt = math.sqrt
maxint=10**21
def ceil(a, b):
    a = -a
    k = a // b
    k = -k
    return k
# arr=list(map(int, input().split()))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
def strinp(testcases):
    k = 5
    if (testcases == -1 or testcases == 1):
        k = 1
    f = str(input())
    f = f[2:len(f) - k]
    return f


def main():
    n=int(input())
    arr=list(map(int, input().split()))
    mi=arr[0]
    g=0
    for i in range(n):
        g=gcd(g,arr[i])
    if(g!=mi):
        print(-1)
        return()
    print(g,end=' ')
    for i in range(1,n):
        print(arr[i],g,end=' ')
main()
