Алиса и Боб играют в игру. Имеется список из \(n\) булевых значений, каждое из которых равняется либо true, либо false, заданный в виде бинарной строки\(^{\text{∗}}\) длины \(n\) (где \(\texttt{1}\) представляет true, а \(\texttt{0}\) представляет false). Изначально между булевыми значениями нет никаких операторов.
Алиса и Боб будут поочерёдно ставить между булевыми значениями операторы and (обозначающие логическое «И») и операторы or (обозначающие логическое «ИЛИ»), причём Алиса будет ходить первой. Таким образом, игра будет состоять из \(n-1\) ходов, поскольку в списке \(n\) булевых значений. Алиса стремится к тому, чтобы итоговое значение было равно true, а Боб — к тому, чтобы оно было равно false. По данному списку булевых значений определите, выиграет ли Алиса, если оба игрока будут играть оптимально.
Чтобы вычислить итоговое значение выражения, выполняйте следующие шаги, пока выражение не будет состоять только из одного true или false:
- Если условие содержит операторы and, выберите любой из них и замените окружающее его подвыражение его значением.
- В противном случае условие содержит операторы or. Выберите любой из них и замените подвыражение, окружающее оператор or, его значением.
Например, выражение
true or false and false имеет значение
true or (false and false) \(=\) true or false \(=\) true. Можно показать, что значение любого составного выражения определено однозначно.
Выходные данные
Для каждого набора входных данных выведите «YES« (без кавычек), если Алиса выиграет, и «NO» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом наборе входных данных Алиса может поместить and между двумя булевыми значениями. Игра закончится, так как других мест для размещения операторов нет, и Алиса выиграет, потому что true and true равняется true.
Во втором наборе входных данных Алиса может поместить or между левым false и средним true. Боб может поместить and между средним true и правым false. Выражение false or true and false равняется false.
Обратите внимание, что эти примеры могут не быть оптимальными стратегиями для Алисы или Боба.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
11
3
010
12
101111111100
10
0111111011
8
01000010
|
YES
NO
YES
YES
NO
|