Sort Primes and Composites

In this problem, you are given a list of integers. Your task is to rearrange the list so that all prime numbers appear at the beginning in ascending order, followed by all composite numbers (i.e., non-prime integers greater than 1) in descending order. Note that numbers less than or equal to 1 should be ignored in both categories.

For example, if the input list is [7, 8, 4, 13, 18, 15, 3], the output should be [3, 7, 13, 18, 15, 8, 4].

The function should work as follows:

(\text{Let } \mathcal{P} = {n \in \mathbb{N} : n > 1 \text{ and } n \text{ is prime}}) and (\mathcal{C} = {n \in \mathbb{N} : n > 1 \text{ and } n \text{ is composite}}).

Sort (\mathcal{P}) in ascending order and (\mathcal{C}) in descending order, and output the concatenation (\mathcal{P}) followed by (\mathcal{C}).

inputFormat

The input is given from standard input (stdin) in the following format:

The first line contains a single integer (N), which represents the number of elements in the list. The second line contains (N) integers separated by spaces.

outputFormat

The output should be printed to standard output (stdout) as a single line containing the rearranged list of integers separated by a single space.## sample

7
7 8 4 13 18 15 3

3 7 13 18 15 8 4