У вас есть последовательность \(a\) длины \(n\), состоящая из цифр \(0\) и \(1\).
Вы можете выполнять следующую операцию над этой последовательностью:
- выбрать индекс \(i\) от \(1\) до \(n-2\) (включительно);
- одновременно заменить значения \(a_{i}\), \(a_{i+1}\), \(a_{i+2}\) на \(a_{i} \oplus a_{i+1} \oplus a_{i+2}\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Найдите последовательность из
не более чем
\(n\) операций, после которой все элементы
\(a\) будут равны
\(0\), или определите, что это невозможно.
Можно показать, что если существует последовательность операций некоторой длины такая, что после ее выполнения все элементы \(a\) будут равны \(0\), то существует и последовательность длины не более \(n\).
Выходные данные
Для каждого набора входных данных:
- если нет способа сделать все элементы \(a\) равными \(0\), выполнив описанную операцию несколько раз, выведите «NO»;
- в противном случае в первой строке выведите «YES», во второй строке выведите \(k\) (\(0 \le k \le n\)) — количество операций над \(a\) в вашем решении, а затем в третьей строке выведите последовательность \(b_1, b_2, \dots, b_k\) (\(1 \le b_i \le n - 2\)) — индексы, которые вы выбираете.
Если существует несколько решений, выведите любое из них.
Примечание
В первом примере последовательность содержит только числа \(0\), поэтому ничего не нужно делать.
Во втором примере мы можем преобразовать \([1, 1, 1, 1, 0]\) в \([1, 1, 0, 0, 0]\), а затем в \([0, 0, 0, 0, 0]\), сначала выполнив операцию, начиная с третьего элемента \(a\), а потом начиная с первого элемента \(a\).
В третьем примере независимо от того, сделаем ли мы первую операцию, начиная с первого или второго элемента \(a\), мы получим \([1, 1, 1, 1]\), что не может быть преобразовано в \([0, 0, 0, 0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
0 0 0
5
1 1 1 1 0
4
1 0 0 1
|
YES
0
YES
2
3 1
NO
|