Дан массив \(a\) длины \(n\), состоящий из нулей и единиц.
Можно несколько раз выполнить следующую операцию, состоящую из двух шагов:
- Взять произвольные целые числа \(1 \le x < y < z \le n\), образующие арифметическую прогрессию (\(y - x = z - y\)).
- Поменять значения \(a_x, a_y, a_z\) на противоположные (т.е. \(1\) заменить на \(0\), \(0\) заменить на \(1\)).
Определите, возможно ли обнулить все элементы массива. Если возможно, то выведите сами операции, причём их количество не должно превышать \((\lfloor \frac{n}{3} \rfloor + 12)\). Здесь \(\lfloor q \rfloor\) означает число \(q\), округленное вниз. Можно показать, что если можно обнулить все элементы массива, то можно их обнулить и не более чем за такое количество операций.
Выходные данные
В первой строке выведите «YES» (без кавычек), если ответ существует, и «NO» (без кавычек) иначе. Вы можете выводить каждую букву в любом регистре (строчную или заглавную).
Если ответ существует, то во второй строке выведите целое число \(m\) (\(0 \le m \le (\lfloor \frac{n}{3} \rfloor + 12)\)) — количество операций в ответе.
Далее в (\(i + 2\))-й строке выведите \(i\)-ю операцию — числа \(x_i, y_i, z_i\). Допустимо выводить эти три числа в произвольном порядке.
Примечание
Изменения массива в первом тесте в авторском решении:
- 1 1 0 1 1 (начальное состояние)
- 0 1 1 1 0 (поменялись значения у первого, третьего и пятого элемента)
- 0 0 0 0 0 (поменялись значения у второго, третьего и четвёртого элемента)
Возможны и другие ответы. В этом тесте количество операций не должно превышать \(\lfloor \frac{5}{3} \rfloor + 12 = 1 + 12 = 13\).
Во втором тесте единственная доступная операция — это поменять значения всех элементов на противоположные. Следовательно, можно получить массивы 0 1 0 и 1 0 1, но нельзя обнулить все элементы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 1 0 1 1
|
YES
2
1 3 5
2 3 4
|
|
2
|
3
0 1 0
|
NO
|