Logical Moos

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

A phrase of the form x OPERATOR y, where $x$ and $y$ are each true or false and OPERATOR is and or or, evaluates as follows:

• x and y is true if both $x$ and $y$ are true, and false otherwise.
• x or y is true if either $x$ or $y$ is true, and false otherwise.

When FJ evaluates the statement, he follows the precedence rules of Moo Language, which match C++: and takes priority over or. 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.

If several phrases can be evaluated in a given step, the choice does not matter. The statement always evaluates to the same value.

FJ receives $Q$ queries ($1 \leq Q \leq 2 \cdot 10^5$). In each query, he gives two odd integers $l$ and $r$ ($1 \leq l \leq r \leq N$) and deletes the segment from keyword $l$ to keyword $r$ inclusive. He wants to replace the deleted segment with a single true or false so that the whole statement evaluates to a given value. Determine whether this is possible.

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

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

Each of the following $Q$ lines contains two integers $l$ and $r$ and a string true or false, the value the whole statement should have after the replacement.

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