Дан массив из \(n\) чисел. Требуется разбить все числа на два множества таким образом, чтобы НОД всех чисел первого множества был равен единице и НОД всех чисел второго множества был равен единице.
НОД множества чисел — наибольшее целое число, делящее все числа из множества.
Оба множества должны быть непустыми.
Выходные данные
В первой строке выведите «YES» (без кавычек), если разбить числа на два множества требуемым образом возможно, или «NO» (без кавычек) в противном случае.
Если разбить числа на два множества возможно, во второй строке выведите \(n\) чисел, где \(i\)-е число равно \(1\), если элемент \(a_i\) должен оказаться в первом множестве, и \(2\) в противном случае.
Если существует несколько решений, вы можете вывести любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 3 6 7
|
YES
2 2 1 1
|
|
2
|
5
6 15 35 77 22
|
YES
2 1 2 1 1
|
|
3
|
5
6 10 15 1000 75
|
NO
|