Дан массив \(A = [a_1, a_2, \ldots, a_n]\), содержащий \(n\) натуральных чисел.
Требуется раскрасить элементы массива в два цвета таким образом, чтобы не существовало двух элементов \(x\) и \(y\) одного цвета, таких что \(x\) нацело делился на \(y\) и выполнялось равенство \(\frac{x}{y} = p\), где \(p\) — простое число. Гарантируется, что такая раскраска существует.
Напомним, что целое число \(p > 1\) называется простым, если оно имеет ровно два делителя: \(1\) и \(p\).
Формат входных данных
Первая строка содержит одно целое число \(n\) (\(1 \le n \le 100\,000\)) — количество элементов в массиве.
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)) — элементы массива.
Формат выходных данных
Выведите описание разбиения массива на два множества в следующем формате.
Выведите \(n\) целых чисел, \(i\)-е из которых равняется \(1\), если элемент \(a_i\) надо раскрасить в первый цвет и \(2\), если элемент \(a_i\) надо раскрасить во второй цвет.
Если существует несколько подходящих раскрасок, вы можете вывести любую из них.
В первом примере есть два элемента первого цвета: \(2\) и \(3\), и два элемента второго цвета: \(1\) и \(4\). Элементы первого цвета не делятся нацело друг на друга. \(4\) нацело делится на \(1\), но их отношение не является простым числом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 3 4
|
2 1 1 2
|
|
2
|
1
20
|
1
|