시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 512 MB111100.000%

문제

Loznica is a city in Serbia, famous by history, culture, pleasant weather... and lottery! Lottery in Loznica is held with following rules:

  • Ballot contains combination of $N$ natural numbers, smaller than $10^{18}$ will be picked.
  • In this lottery, numbers can repeat and order of them is important.

Aljoha, the hero of our story, using some obscure utilities, managed to find out some information about the next winning ballot. Let the future combination be $L_{i}$, $1 \leq i \leq N$. Aloha managed to find out an array containing $N-1$ numbers, in which the $i$th number $A_{i}$ represents the largest number which divides both $L_{i}$ and $L_{i+1}$.

Now Aljoha wants to bet, and for that noble goal he needs help. Print one combination which satisfies the constraints or $-1$, if that kind of combination doesn't exist. If there are more combinations that satisfy given constraints, print any of them. Note that only combinations in which all numbers are strictly smaller than $10^{18}$ are valid.

입력

First line contains number $N$ ($1 \leq N \leq 10^5$), length of combination.

Second line contains $N-1$ positive integers not greater than $10^9$, describing the information that Aljoha found out.

출력

Print $N$ numbers, strictly less than $10^{18}$, describing some combination which satisfies the constraints or $-1$ if there is no such combination.

예제 입력 1

4
3 4 10

예제 출력 1

3 12 20 10

예제 입력 2

4
3 4 6

예제 출력 2

-1