print1468. Group by GCD

printGroup by GCD

Ограничения: время – 5s/10s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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_1\ a_2…\ 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^8`

Sample Input 1

2
3 5

Sample Output 1

3 0 5

Sample Input 2

4
2 2 6 8

Sample Output 2

2 6 2 0 8

Sample Input 3

3
3 4 5

Sample Output 3

-1
Source: NEERC ICPC, Far Eastern subregion, 2009
loading