У Фермера Джона есть булевское выражение длиной в \(N\) слов
(\(1 \leq N < 2 \cdot 10^5\), \(N\) нечётное). Только \(\texttt{true}\) or \(\texttt{false}\)
появляются на нечётных позициях, и только \(\texttt{and}\) и \(\texttt{or}\) появляются на чётных позициях.
Фраза вида \(x\text{ OPERATOR }y\), где \(x\) и \(y\) или \(\texttt{true}\) или \(\texttt{false}\),
а \(\text{OPERATOR}\) есть \(\texttt{and}\) или \(\texttt{or}\), вычисляется следующим образом:
- \(x\texttt{ and }y\): Это вычисляется в true если оба \(x\) и \(y\) true, иначе в false.
- \(x\texttt{ or }y\): Это вычисляется в true если или \(x\) или \(y\) true, иначе в false.
При вычислении выражения ФД действует так:
Аналогично C++, \(\texttt{and}\) имеет более высокий приоритет чем \(\texttt{or}\).
Более подробно: для вычисления выражения повторяется следующий шаг пока в выражении не останется
ровно одно слово.
- Если выражение содержит \(\texttt{and}\), выбирается любой из них и фраза, окружающая его,
заменяется её вычислением.
- Иначе, выражение содержит \(\texttt{or}\). Выбирается любой из них и фраза, окружающая его,
заменяется её вычислением.
Можно доказать, что порядок вычислений не важен, выражение всегда будет вычислено к одному
и тому же результату.
У ФД есть \(Q\) \((1 \leq Q \leq 2 \cdot 10^5)\) запросов. В каждом запросе она даёт Вам два целых числа
\(l\) и \(r\) (\(1 \leq l \leq r \leq N\), \(l\) и \(r\) оба нечётные), и удаляет сегмент от ключевого слова
\(l\) до ключевого слова \(r\) включительно.
Он хочет заменить удалённый сегмент одним \(\texttt{true}\) или \(\texttt{false}\) так, чтобы
оставшееся выражение вычислялось к определённому булевскому значению. Помогите ФД определить, возможно ли это.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(Q\).
Следующая строка содержит \(N\) слов, корректное булевское выражение.
Последующие \(Q\) строк содержат два целых числа \(l\) и \(r\), и строку
\(\texttt{true}\) или \(\texttt{false}\), обозначающую, что он хочет,
чтобы оставшееся после удаления выражение вычислилось к этому значению.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выедите строку длины \(Q\), где \(i\)-ый символ есть Y если i-ый запрос возможно выполнить
и N в противном случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 7
false and true or true
1 1 false
1 3 true
1 5 false
3 3 true
3 3 false
5 5 false
5 5 true
|
NYYYNYY
|