Logical Moos

문제

Farmer John has a boolean statement that is $NN$ keywords long (, $NN$ odd). Only true or false appear in odd positions, while only and and or appear in even positions.

A phrase of the form $x\text{ OPERATOR }yx\backslash text\{\; OPERATOR\; \}y$, where $xx$ and $yy$ are either true or false, and $\text{OPERATOR}\backslash text\{OPERATOR\}$ is and or or, evaluates as follows:

• $xx$ and $yy$: This evaluates to true if both $xx$ and $yy$ are true, and false otherwise.
• $xx$ or $yy$: This evaluates to true if either $xx$ or $yy$ is true, and false otherwise.

When evaluating the statement, FJ has to take the order of precedence in Moo Language into account. Similar to C++, and takes priority over or. More specifically, to evaluate the statement, repeat the following step until the statement consists of only one keyword.

1. If the statement contains an and, choose any of them and replace the phrase surrounding it with its evaluation.
2. Otherwise, the statement contains an or. Choose any of them and replace the phrase surrounding it with its evaluation.

It may be proven that if multiple phrases can be evaluated during a given step, it does not matter which one is chosen; the statement will always evaluate to the same value.

FJ has $QQ$ $(1\le Q\le 2\cdot {10}^5)(1\; \backslash leq\; Q\; \backslash leq\; 2\; \backslash cdot\; 10^5)$ queries. In each query, he gives you two integers $ll$ and $rr$ ($1\le l\le r\le N1\; \backslash leq\; l\; \backslash leq\; r\; \backslash leq\; N$, $ll$ and $rr$ are both odd), and deletes the segment from keyword $ll$ to keyword $rr$ inclusive. In turn, he wishes to replace the segment he just deleted with just one simple true or false so that the whole statement evaluates to a certain boolean value. Help FJ determine if it's possible!

입력

The first line contains $NN$ and $QQ$.

The next line contains $NN$ strings, a valid boolean statement.

The following $QQ$ lines contain two integers $ll$ and $rr$, and a string true or false, denoting whether he wants the whole statement to evaluate to true or false.

출력

Output a string of length $QQ$, where the $ii$'th character is Y if the $ii$'th query is possible, otherwise N.

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

13 4
false or true and false and false and true or true and false
1 5 false
3 11 true
3 11 false
13 13 true

YNYY