{"problem":{"name":"[USACO24OPEN] Logical Moos B","description":{"content":"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 $\\te","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10274"},"statements":[{"statement_type":"Markdown","content":"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.  \n\nA 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:  \n\n- $x\\texttt{ and }y$: This evaluates to true if both $x$ and $y$ are true, and false otherwise.\n- $x\\texttt{ or }y$: This evaluates to true if either $x$ or $y$ is true, and false otherwise.  \n\nWhen 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.  \n\n1. If the statement contains an $\\texttt{and}$, choose any of them and replace the phrase surrounding it with its evaluation.\n1. Otherwise, the statement contains an $\\texttt{or}$. Choose any of them and replace the phrase surrounding it with its evaluation.  \n\nIt 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.  \n\nFJ 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!\n\n## Input\n\nThe first line contains $N$ and $Q$.  \n\nThe next line contains $N$ strings, a valid boolean statement.  \n\nThe 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.\n\n## Output\n\nOutput a string of length $Q$, where the $i$'th character is Y if the $i$'th query is possible, otherwise N.\n\n[samples]\n\n## Note\n\n##### For Sample 1:\nLet's analyze the first query:  \n\nIf we were to replace delete the segment $[1, 1]$ and replace it with $\\texttt{true}$, then the whole statement becomes:  \n```\ntrue and true or true\n```\n\nWe evaluate the $\\texttt{and}$ keyword from at position $2$ and obtain  \n```\ntrue or true\n```\n\nSince we have no $\\texttt{and}$ keywords left, we have to evaluate the $\\texttt{or}$ keyword. After evaluation, all that is left is  \n```\ntrue\n```\n\nIt can be shown that if we were to replace the segment with $\\texttt{false}$, the statement will still evaluate to $\\texttt{true}$, so we output N since the statement cannot possibly evaluate to $\\texttt{false}$.  \n\nFor the second query, we can replace the segment $[1, 3]$ with $\\texttt{true}$ and the whole statement will evaluate to $\\texttt{true}$, so we output Y.  \n\nFor the third query, since $[1, 5]$ is the whole statement, we can replace it with anything, so we output Y.  \n\n#### SCORING:\n\n- Inputs 3-5: $N,Q\\le 10^2$\n- Inputs 6-8: $N,Q\\le 10^3$\n- Inputs 9-26: No additional constraints.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10274","tags":["模拟","USACO","2024","分类讨论"],"sample_group":[["5 7\nfalse and true or true\n1 1 false\n1 3 true\n1 5 false\n3 3 true\n3 3 false\n5 5 false\n5 5 true","NYYYNYY"],["13 4\nfalse or true and false and false and true or true and false\n1 5 false\n3 11 true\n3 11 false\n13 13 true","YNYY"]],"created_at":"2026-03-03 11:09:25"}}