Дан массив из \(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
500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач