Prime Rearrangement

You are given an array of integers. Your task is to rearrange the array such that all the prime numbers appear at the beginning, while the non-prime numbers remain at the end, preserving their original order.

Recall that a number n is prime if and only if it is greater than 1 and has no positive divisors other than 1 and itself. In mathematical notation, a number n is prime if there does not exist an integer k with \(2 \le k \le \sqrt{n}\) such that \(n \bmod k = 0\).

Your solution should read the input from standard input and output the rearranged array to standard output. Ensure that the prime numbers keep the order in which they initially appear, followed by the non-prime numbers in their original order.

inputFormat

The first line contains a single integer n, the number of elements in the array. The second line contains n space-separated integers representing the array.

Example:

6
11 4 7 10 2 9

outputFormat

Output the rearranged array in a single line, with each number separated by a space.

Example:

11 7 2 4 10 9

## sample

6
11 4 7 10 2 9

11 7 2 4 10 9