Разбиение массива
(Время: 3 сек. Память: 32 Мб Сложность: 43%)
Дан массив A = [a1, a2, ..., an], содержащий n натуральных чисел.
Требуется раскрасить элементы массива в два цвета таким образом, чтобы не существовало двух
элементов x и y одного цвета, таких, что x нацело делился на y и выполнялось равенство x/y = p, где
p – простое число. Гарантируется, что такая раскраска существует.
Напомним, что целое число p > 1 называется простым, если оно имеет ровно два делителя: 1 и p.
Входные данные
Первая строка входного файла INPUT.TXT содержит одно целое число n (1 ≤ n ≤ 100 000) – количество элементов в массиве.
Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 106) – элементы массива.
Выходные данные
В выходной файл OUTPUT.TXT выведите описание разбиения массива на два множества в следующем формате.
Выведите n целых чисел, i-е из которых равняется 1, если элемент ai надо раскрасить в первый
цвет, и 2, если элемент ai надо раскрасить во второй цвет.
Если существует несколько подходящих раскрасок, вы можете вывести любую из них.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
1 2 3 4 | 2 1 1 2 |
| 2 | 1
20 | 1 |
Замечание
В первом примере есть два элемента первого цвета: 2 и 3, и два элемента второго цвета: 1 и 4.
Элементы первого цвета не делятся нацело друг на друга. 4 нацело делится на 1, но их отношение
не является простым числом.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
