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 a1 a2… aN.

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 ≤ ai ≤ 108

Sample tests

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

0.037s 0.008s 15