В ряд выстроены \(n\) ламп с номерами от \(1\) до \(n\), изначально они выключены. Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
- Выбрать две несоседние\({}^\dagger\) лампы, которые в данный момент выключены, и включить их.
Определите, можете ли вы достичь конфигурации \(s\), где \(s_i = 1\) означает, что \(i\)-я лампа включена, а в противном случае \(s_i = 0\).
\({}^\dagger\) Соседними считаются только лампы \(i\) и \(i + 1\) для всех \(1 \le i < n\). Обратите внимание, что лампы \(n\) и \(1\) не являются соседними при \(n \ne 2\).
Выходные данные
Для каждого набора входных данных выведите в отдельной строке «YES», если возможно достичь конфигурацию \(s\) путем применения данной операции любое количество раз. В противном случае выведите «NO».
Примечание
В первом наборе входных данных последовательность операций могла бы быть следующей (обратите внимание, что изначально все элементы \(s\) равны нулю): \(\mathtt{0000000000} \to \mathtt{\color{red}{1}0000000\color{red}{1}0} \to \mathtt{1\color{red}{1}00000\color{red}{1}10} \to \mathtt{110\color{red}{1}0\color{red}{1}0110}\).
В третьем наборе входных данных не нужно выполнять никаких операций.
В четвертом наборе входных данных невозможно выполнить никакую операцию, но нам нужно, чтобы горела первая лампа. Поэтому достичь желаемой конфигурации невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
10
1101010110
10
1001001110
6
000000
1
1
12
111111111111
|
YES
NO
YES
NO
YES
|