Categorize Numbers into Primes and Non-Primes

You are given a list of integers. Your task is to separate the numbers into two lists: one containing all the prime numbers and the other containing all the non-prime numbers.

A prime number is a positive integer that is greater than 1 and has no positive divisors other than 1 and itself. In other words, a number \( n \) is prime if it satisfies:

\( n > 1 \) and for all integers \( d \) such that \(2 \leq d \leq \sqrt{n}\), \( d \) does not divide \( n \) exactly.

If the input list is empty, both output lists should be empty.

inputFormat

The first line of the input contains a single integer \( n \) representing the number of integers in the list. The second line contains \( n \) space-separated integers.

outputFormat

Output two lines. The first line should contain the prime numbers (if any) in the same order as they appear in the input, separated by spaces. The second line should contain the non-prime numbers (if any) in the same order, separated by spaces. If a list is empty, output an empty line for it.

6
1 2 3 4 5 6

2 3 5
1 4 6