Lexicographically Smallest Relatively Prime Sequence Rearrangement

Given a sequence of n positive integers, rearrange the sequence so that every adjacent pair of elements is relatively prime, i.e. their greatest common divisor (gcd) is 1. If multiple valid rearrangements exist, output the lexicographically smallest one (comparing element by element). If no such rearrangement exists, output -1.

Note: Two numbers are relatively prime if their gcd is 1. The lexicographical order means that among all valid sequences, the one that appears first in dictionary order (when compared element-wise) should be printed.

inputFormat

The first line of input contains an integer n, representing the number of elements in the sequence. The second line contains n space-separated integers representing the sequence.

outputFormat

If a valid rearrangement exists, print the lexicographically smallest valid sequence as n space-separated integers on a single line. Otherwise, print -1.## sample

4
2 3 4 5

2 3 4 5