Prime-Nonprime Reordering

Given an integer ( N ) and a list of ( N ) integers, rearrange the list such that all prime numbers appear first followed by all non-prime numbers. Within each group, the numbers must be sorted in descending order.

A number ( x ) is considered prime if ( x > 1 ) and its only divisors are 1 and ( x ). Equivalently, one can check that for any integer ( p ) with ( 2 \leq p \leq \sqrt{x} ), ( x ) is not divisible by ( p ).

For example, if the input list is:

10 29 3 20 17 5 18 2 11 19

The output should be:

29 19 17 11 5 3 2 20 18 10

All input is read from standard input and all output is written to standard output.

inputFormat

The first line contains an integer ( N ) indicating the number of elements. The second line contains ( N ) space-separated integers.

outputFormat

Output the rearranged list as space-separated integers on a single line, where the prime numbers (sorted in descending order) come first, followed by the non-prime numbers (also sorted in descending order).## sample

10
10 29 3 20 17 5 18 2 11 19

29 19 17 11 5 3 2 20 18 10