Winning Ballot

Time limit1sMemory limit512 MB

Summary

Given N-1 values where A_i is the gcd of consecutive terms, reconstruct a sequence of N numbers below 10^18, or report that none exists.

Level: Medium7 of 10
Topics: Number theory, Math, Greedy, Implementation
Solved: No attempts yet

Problem

Loznica is a city in Serbia, famous for its history, culture, pleasant weather, and lottery. The lottery in Loznica follows these rules:

A ballot holds a combination of $N$ natural numbers, each smaller than $10^{18}$ .
Numbers may repeat, and their order matters.

Aljoha, the hero of our story, used some obscure utilities to learn information about the next winning ballot. Let the future combination be $L\_{i}$ , $1 \leq i \leq N$ . Aljoha learned an array of $N-1$ numbers, in which the $i$ th number $A\_{i}$ is the largest number that divides both $L\_{i}$ and $L\_{i+1}$ .

Now Aljoha wants to bet, and for that noble goal he needs help. Print one combination that satisfies the constraints, or $-1$ if no such combination exists. If more than one combination satisfies the constraints, print any of them. Only combinations in which every number is strictly smaller than $10^{18}$ are valid.

Input

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

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

Output

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

Examples2

Example 1
Input
```
4
3 4 10
```
Expected output
```
3 12 20 10
```
Example 2
Input
```
4
3 4 6
```
Expected output
```
-1
```