문제

Farmer John has a boolean statement that is $N$ keywords long ($1 \leq N < 2 \cdot 10^5$, $N$ odd). Only $\texttt{true}$ or $\texttt{false}$ appear in odd positions, while only $\texttt{and}$ and $\texttt{or}$ appear in even positions.

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

$x\texttt{ and }y$: This evaluates to true if both $x$ and $y$ are true, and false otherwise.$x\texttt{ or }y$: This evaluates to true if either $x$ or $y$ 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++, $\texttt{and}$ takes priority over $\texttt{or}$. More specifically, to evaluate the statement, repeat the following step until the statement consists of only one keyword.

If the statement contains an $\texttt{and}$, choose any of them and replace the phrase surrounding it with its evaluation.Otherwise, the statement contains an $\texttt{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 $Q$ $(1 \leq Q \leq 2 \cdot 10^5)$ queries. In each query, he gives you two integers $l$ and $r$ ($1 \leq l \leq r \leq N$, $l$ and $r$ are both odd), and deletes the segment from keyword $l$ to keyword $r$ inclusive. In turn, he wishes to replace the segment he just deleted with just one simple $\texttt{true}$ or $\texttt{false}$ so that the whole statement evaluates to a certain boolean value. Help FJ determine if it's possible!

입력

The first line contains $N$ and $Q$.

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

The following $Q$ lines contain two integers $l$ and $r$, and a string $\texttt{true}$ or $\texttt{false}$, denoting whether he wants the whole statement to evaluate to true or false.

출력

Output a string of length $Q$, where the $i$'th character is Y if the $i$'th query is possible, otherwise 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

예제 출력 1

NYYYNYY

예제 입력 2

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

예제 출력 2

YNYY

점수

Inputs 3-5: $N,Q\le 10^2$Inputs 6-8: $N,Q\le 10^3$Inputs 9-26: No additional constraints.