题目描述

Farmer John 有一个布尔语句，包含 $N$ 个关键字。奇数位置仅出现 true 或 false偶数位置上仅出现 and 或 or。

一个$xOPERATORy$形式的短语，其中$x$和$y$为true或false,而$OPERATOR$,为and 或or ，按如下规则求值:

x and y:如果$x$和$y$均为 true，则求值结果为 true，否则为 false。

x or y:如果$x$或$y$为true，则求值结果为 true，否则为 false.

在求值该语句时，F 必须考虑 Moo 语言中的运算符优先级。与 C++类似，and 优先级高于 or。

更具体地说，在求值该语句时，重复以下步骤直至该语句仅包含一个关键字。

1.如果语句中包含 and，选择其中任意一个，并将其周围的短语替换为其求值结果

2.否则，该语句包含 or。选择其中任意一个，并将其周围的短语替换为其求值结果。

可以证明，如果在指定的一个步骤中可以求值多个短语，那么选择哪一个求值并不重要;

该语句最终的求值结果将始终相同。

FJ有 $Q$个询问。在每个询问中，他给你两个整数$l$和$r$并删除关键字$l$到关键字$r$之间的段。

反过来，他希望用一个简单的 true 或 false 替换他刚刚删除的段，以使整个语句的求值结果为某个指定的布尔值。

帮助FJ判断是否可行!

输入

输入的第一行包含 $N$ 和 $Q$。

下一行包含 $N$ 个字符串，为一个合法的布尔语句。

以下$Q$行，每行包含两个整数$l$和$r$，以及一个字符串 true 或 false，表示他希望整个语句的求值结果为 true 还是false。

输出

输出一个长度为 $Q$ 的字符串，其中如果第 $i$ 个询问的结果为可能，则第 $i$个字符为 Y，否则为 N。

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

NYYYNYY

样例解释

我们来分析第一个询问: 如果我们删除段「1,1]并替换为 true，那么整个语句将变为: true and true or true

我们对位置 2 处的 and关键字求值，得到true or true

由于我们没有剩下的 and 关键字，我们必须求值 or 关键字。求值结束后，余下的是true

可以证明，如果我们用 false 替换该段，该语句仍将求值为 true，因此我们输出N，因为该语句不可能求值为false.

对于第二个询问，我们可以将段「1,3|替换为 true，整个语句将求值为 true，因此我们输出 Y。

对于第三个询问，由于「1,5]是整个语句，我们可以将其替换为任意内容，因此我们输出 Y。

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

YNYY

提示

测试点$3-5:N,Q≤ 10^2.$

测试点$6-8:N,Q≤ 10^3$

测试点$9-26:$ $1 \leq N,Q \leq 2 \times 10^5$

$1 \leq l \leq r \leq N,l和R$均为奇数