Условие:Вася любит решать задачи на темы, которые проходили на упражнениях кружка

Условие:
Вася любит решать задачки на темы, которые проходили на упражнениях кружка по математике. Он
познакомился с темой, связанной с делимостью чисел. По дороге домой из школы он записывал все
числа, которые повстречались ему на пути. Получился набор из N целых чисел.
Ему занимательно, можно ли разбить этот набор не более чем на три группы так, чтоб в каждой
группе все числа имели общий делитель, больший 1. Помогите ему решить эту задачку.

Формат входных данных

В первой строке входного файла записано одно целое число N (1 N 105). 2-ая строка
содержит N положительных целых чисел, записанных через пробел, встреченных Васей по дороге
домой. Каждое число не превосходит 10^9.

Формат выходных данных

В первую строчку выходного файла требуется вывести строчку Possible, если разбить числа требуемым
образом можно, и Impossible, если нельзя.
Если разбиение существует, то во вторую строчку нужно вывести N чисел через пробел,
каждое из которых одинаково 1, 2 или 3 и значит номер группы в разбиении соответствующего числа.
Если разбиений существует несколько, то нужно вывести данные для любого из них.

Образцы:
Вход:

5
12 7 18 5 10

Выход:
Possible
1 2 1 3 1

Вход:
4
2 1 3 4

Выход:
Impossible


Замечание
В первом тесте числа разбиваются на три группы так: 12 и 18 (оба делятся на 6), 7, и в конце концов,
5 и 10, так как оба делятся на 5.