Problem Description

Farmer John has a boolean statement containing $N$ keywords ($1 \le N < 2 \cdot 10^5$, $N$ is odd). Odd positions contain only $\texttt{true}$ or $\texttt{false}$, and even positions contain only $\texttt{and}$ or $\texttt{or}$.

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

• $x \operatorname{and} y$: The result is $\texttt{true}$ if both $x$ and $y$ are $\texttt{true}$, otherwise $\texttt{false}$.
• $x \operatorname{or} y$: The result is $\texttt{true}$ if either $x$ or $y$ is $\texttt{true}$, otherwise $\texttt{false}$.

When evaluating the statement, FJ must consider the operator precedence in Moo language. Similar to C++, $\operatorname{and}$ has higher precedence than $\operatorname{or}$. Specifically, the statement is evaluated by repeating the following steps until it contains only one keyword:

1. If the statement contains $\operatorname{and}$, select any one and replace the surrounding phrase with its evaluation result.
2. Otherwise, the statement contains $\operatorname{or}$. Select any one and replace the surrounding phrase with its evaluation result.

It can be proven that if multiple phrases can be evaluated in a specified step, the choice of which to evaluate does not matter; the final evaluation result of the statement will always be the same.

FJ has $Q$ ($1 \le Q \le 2 \cdot 10^5$) queries. In each query, he gives you two integers $l$ and $r$ ($1 \le l \le r \le N$, both $l$ and $r$ are odd) and removes the segment between keywords $l$ and $r$. Conversely, he wants to replace the segment he just removed with a simple $\texttt{true}$ or $\texttt{false}$ to make the entire statement evaluate to a specified boolean value. Help FJ determine if it is possible!

Input Format

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

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

The following $Q$ lines, each containing two integers $l$ and $r$, and a string $\texttt{true}$ or $\texttt{false}$, indicate that he wants the entire statement to evaluate to $\texttt{true}$ or $\texttt{false}$.

Output Format

Output a string of length $Q$, where the $i$-th character is Y if the $i$-th query is possible, otherwise N.

Sample Input and Output

Input Sample #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

Output Sample #1

NYYYNYY

Input Sample #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

Output Sample #2

YNYY

Notes/Hints

Sample Explanation 1

Let's analyze the first query:

If we remove the segment $[1,1]$ and replace it with $\texttt{true}$, the entire statement becomes:

$\texttt{true and true or true}$

We evaluate the $\texttt{and}$ keyword at position $2$, resulting in:

$\texttt{true or true}$

Since there are no remaining $\texttt{and}$ keywords, we must evaluate the $\texttt{or}$ keyword. After evaluation, we are left with:

$\texttt{true}$

It can be proven that if we replace the segment with $\texttt{false}$, the statement will still evaluate to $\texttt{true}$, so we output N because the statement cannot evaluate to false.

For the second query, we can replace the segment $[1,3]$ with $\texttt{true}$, making the entire statement evaluate to $\texttt{true}$, so we output Y.

For the third query, since $[1,5]$ is the entire statement, we can replace it with either $\texttt{true}$ or $\texttt{false}$, so we output Y.

Test Case Properties

• Test cases $3-5$: $N, Q \le 10^2$.
• Test cases $6-8$: $N, Q \le 10^3$.
• Test cases $9-26$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分