Sort Array with Primes First

You are given an array of n integers. Your task is to rearrange the array so that all prime numbers appear first, followed by the non-prime numbers. The relative order of the prime numbers among themselves and the relative order of the non-prime numbers among themselves should remain unchanged.

A prime number is defined as an integer greater than 1 that has no positive divisors other than 1 and itself. In mathematical terms, a number \(n\) is prime if \(n > 1\) and \(\forall d \in \mathbb{N} \ (d|n \Rightarrow d = 1 \text{ or } d = n)\).

Implement a solution that reads the array from standard input and writes the rearranged array to standard output.

inputFormat

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

• The first line contains an integer \(n\) representing the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the array elements.

outputFormat

Output the rearranged array as a single line of space-separated integers. The order must first include all the prime numbers (in their original order), followed by the non-prime numbers (also in their original order).

## sample

6
1 7 4 2 10 3

7 2 3 1 4 10

</p>