Problem D. Group by GCD ≡

Author:	A. Klenin		Time limit:	1 sec
Input file:	input.txt		Memory limit:	64 Mb
Output file:	output.txt

Statement

Given N positive integers, divide them in two disjoint non-empty groups in such a way that the greatest common divisor of each group is greater than 1.

Input file format

Input file contains integer N, followed by N integers a₁ a₂… a_N.

Output file format

Output file must contain numbers belonging to the first group, followed by 0 and then by numbers belonging to the second group. If there is no solution, output a single number −1. If there is more than one solution, output any of them.

Constraints

2 ≤ N ≤ 1000, 2 ≤ a_i ≤ 10⁸

Sample tests

No.	Input file (input.txt)	Output file (output.txt)
1	2 3 5 copy	3 0 5 copy
2	4 2 2 6 8 copy	2 6 2 0 8 copy
3	3 3 4 5 copy	-1 copy

---