tuni2

24.06.2023 02:18

Информатика

Есть ответ 👍

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