A maintenance shaft in an old factory holds a row of gears, each stamped with a tooth count. Whenever two gears with different tooth counts sit right next to each other on the shaft, the mesh grinds and slips, so the crew always slides in a small synchronizer gear between them. A synchronizer's own tooth count is fixed by the two gears it sits between: it always equals their greatest common divisor. The crew installs exactly one synchronizer after every gear except the last one, so the shaft ends up longer than it started. Given the tooth counts of the original gears in shaft order, report the tooth counts of the entire shaft — originals and synchronizers together — in the final mounting order.

Input format

Line 1: a single integer n, the number of original gears. Line 2: n space-separated integers, the tooth counts of the original gears in shaft order.

Output format

Print one line containing the tooth counts of the full shaft after every synchronizer gear has been installed, space-separated, in shaft order. The full shaft has 2n - 1 gears in total (just the one original gear if n = 1).

Constraints

• 1 ≤ n ≤ 5000
• 1 ≤ tooth count ≤ 1000

4
18 6 10 3

18 6 6 2 10 1 3

1
7

7