One of your friends, Ozi has come up with a new sorting system, prima sort. In this system, to sort an array \(A\) you use the sorted array of primes. [2, 3, 5, 7, 11, ..]

Using the prime array you generate an empty list for each prime and then add each element of the array \(A\) to a prime's list. While adding an element to a prime list, you should be sure that that prime is the minimum prime that divides the element.

In the end, you would have lists of numbers. And, you are expected to print those lists in the increasing order of primes.

Minimum primes that can be divided to the numbers are \([3(39), 2(12), 2(25), 2(4), 3(9)]\). Pushing those numbers to corresponding lists:

• 2 -> \([4, 12]\)
• 3 -> \([9, 39]\)
• 5 -> \([25]\)

The concatenation of those lists is the requested answer.

If there are 1's in the array, they should be located at the start of the array.

Input

The first line only consists of the number \(N\).

The next line includes \(N\) positive integers.

• \(1 \leq \mathbf{N} \leq 10^{5}\)
• \(1 \leq \mathbf{A_i} \leq 10^{5}\)

Output

Output the prima sorted array in a single line.

Examples

Input:

5
39 12 25 4 9

Output:

4 12 9 39 25

Input:

7
3 5 7 12 8 45 90

Output:

8 12 90 3 45 5 7