USACO 2024 US OPEN CONTEST, BRONZE

Problem 1. Logical Moos

Farmer John has a boolean statement that is \( N \) keywords long (\( N \) 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 either true or false, and OPERATOR is and or or, evaluates as follows:

• and: This evaluates to true if both \( x \) and \( y \) are true, and false otherwise.
• or: 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++, and takes priority over or. To evaluate the statement, repeat the following steps 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 can 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 \) queries. In each query, he gives you two integers \( l \) and \( r \) (\( 1 \leq l \leq r \leq N \); both \( l \) and \( r \) are odd), and deletes the segment from keyword \( l \) to keyword \( r \) inclusive. He wishes to replace the deleted segment 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!

Input Format

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 true or false, denoting whether he wants the whole statement to evaluate to true or 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

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

Sample Output

NYYYNYY

Explanation of Sample

Let's analyze the first query:

If we delete the segment at position 1 and replace it with false, the whole statement becomes:

true and true or true

We evaluate the and operator and obtain:

true or true

Since we have no and keywords left, we evaluate the or keyword. After evaluation, all that is left is true. Since we cannot evaluate to false, we output N.

For the second query, we can replace the segment with true, and the statement will evaluate to true, so we output Y.

For the third query, since false is the entire statement, we can replace it with anything, so we output Y.

Sample Input

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

Sample Output

YNYY

Scoring:

• Inputs 3-5: \( N, Q \leq 10^2 \)
• Inputs 6-8: \( N, Q \leq 10^3 \)
• Inputs 9-26: No additional constraints.