Условие: Вася любит решать задачи на темы, которые проходили на занятиях кружка по математике. Он познакомился с темой, связанной с делимостью чисел. По дороге домой из школы он записывал все числа, которые встретились ему на пути. Получился набор из 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.