Mayank and his girlfriend decided to go out for a movie. In interval, they found out an array A of numbers.As Mayank is fond of prime numbers. So, he decided to separate the prime numbers from the array. His girlfriend knew that this task is a cakewalk for him. She wanted Mayank to prove his love for her. So, she decided to test him by sort the array using following rules:

1. All prime numbers must be shifted to left while composite numbers are shifted towards right.

2. Prime numbers should be arranged in decreasing order.

3. Composite numbers should be arranged in increasing order. As you are best friend of mayank and he really loves her. He ask for your help. Please help him to sustain his relationship.

INPUT:

First line of input contain a number N - size of array.

Second line conatins N space separated numbers A[i].

OUTPUT:

Print all the elements of the array in the required sorted order.

Constraints:

1<=n<=10000

1<=A[i]<=10000000

Sample input:

10 1 2 3 4 5 6 7 8 9 10

Sample output:

7 5 3 2 1 4 6 8 10

Explaination:

Prime numers are 1,2,3,5,7 and Composite numbers are 4,6,8,9,10 By 2nd condition Prime numbers are arranged as 7,5,3,2,1 and by 3rd condition Composite numbers are arranged as: 4,6,8,9,10 Now by 1st condition they are combined to form the required output.