Сегодня Маша пришла на урок математики. Зайдя в класс, она увидела на доске две последовательности целых чисел одинаковой длины \(n - 1\) и задание учителя, записанное ниже. Обозначим члены первой последовательности как \(a_i\) (\(0 \le a_i \le 3\)), а члены второй последовательности как \(b_i\) (\(0 \le b_i \le 3\)).
Маша быстро решила задачу учителя, и ей стало интересно, существует ли такая последовательность длины \(n\), члены которой обозначим как \(t_i\) (\(0 \le t_i \le 3\)), что для любого \(i\) (\(1 \le i \le n - 1\)) верно:
- \(a_i = t_i | t_{i + 1}\) (где \(|\) обозначает операцию побитового ИЛИ) и
- \(b_i = t_i \& t_{i + 1}\) (где \(\&\) обозначает операцию побитового И).
Такая задача оказалась слишком сложной для Маши, поэтому она просит Вас, как лучшего друга, проверить, существует ли такая последовательность \(t_i\) длины \(n\) подходящая под условия, описанные выше. Если такая последовательность существует, то Маша также хочет посмотреть на нее. Если есть несколько таких последовательностей, то Вы можете показать Маше любую из них.
Выходные данные
В первой строке выведите одно слово: «YES» (без кавычек), если существует такая последовательность \(t_i\), подходящая под условия, или «NO» (без кавычек), если такой последовательности не существует.
Если последовательность существует, то во второй строке выведите \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(0 \le t_i \le 3\)) — последовательность, подходящая под ограничения из условия.
Если существует несколько ответов, выведите любой из них.
Примечание
В первом примере мы можем убедиться, что выведенная последовательность подходит под условия:
- \(t_1 | t_2 = (01_2) | (11_2) = (11_2) = 3 = a_1\) и \(t_1 \& t_2 = (01_2) \& (11_2) = (01_2) = 1 = b_1\);
- \(t_2 | t_3 = (11_2) | (10_2) = (11_2) = 3 = a_2\) и \(t_2 \& t_3 = (11_2) \& (10_2) = (10_2) = 2 = b_2\);
- \(t_3 | t_4 = (10_2) | (00_2) = (10_2) = 2 = a_3\) и \(t_3 \& t_4 = (10_2) \& (00_2) = (00_2) = 0 = b_3\).
Во втором примере такой последовательности не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 3 2
1 2 0
|
YES
1 3 2 0
|
|
2
|
3
1 3
3 2
|
NO
|