F. GCD-группы 2
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив из $$$n$$$ чисел. Требуется разбить все числа на два множества таким образом, чтобы НОД всех чисел первого множества был равен единице и НОД всех чисел второго множества был равен единице.

НОД множества чисел — наибольшее целое число, делящее все числа из множества.

Оба множества должны быть непустыми.

Входные данные

В первой строке записано число $$$n$$$ ($$$2 \leq n \leq 10^5$$$).

Во второй строке записаны $$$n$$$ чисел $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — элементы массива.

Выходные данные

В первой строке выведите «YES» (без кавычек), если разбить числа на два множества требуемым образом возможно, или «NO» (без кавычек) в противном случае.

Если разбить числа на два множества возможно, во второй строке выведите $$$n$$$ чисел, где $$$i$$$-е число равно $$$1$$$, если элемент $$$a_i$$$ должен оказаться в первом множестве, и $$$2$$$ в противном случае.

Если существует несколько решений, вы можете вывести любое.

Примеры
Входные данные
4
2 3 6 7
Выходные данные
YES
2 2 1 1
Входные данные
5
6 15 35 77 22
Выходные данные
YES
2 1 2 1 1
Входные данные
5
6 10 15 1000 75
Выходные данные
NO