Question

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

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

В первой строке входного файла записано одно целое число N (1 ⩽ N ⩽ 105). Вторая строка
содержит 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.

Answer 1

Формула вывода ndiv10^7. По крайней мере я так решил. Ответ - 1 получается