题目描述

给定一个长度不超过$2 \times 10^5$仅有字母$'N','O','I'$构成的字符串，$Bob$想知道该字符串能否通过下面的操作变成单个字母$‘N’$（操作次数及顺序不限）：

1. 选择两个相邻且相等字母将其全部删除；
2. 选择一个字母，将其替换成另外两个字母，两字母顺序任意。

$Bob$为了增加难度，给出$Q$次询问，询问子串$S[l...r]$能否通过上面操作得到一个$'N'$，如果可以输出$'Y'$，否则输出$'N'$。

输入格式

第一行，一个字符串$S$;

第二行，一个整数$q$;

接下来$q$行，每行两个整数$l$和$r$ $(1 \le l \le r \le |S|)$,$|S|$表示字符串长度。

输出格式

输出一个长为 $q$的字符串，如果第 $i$ 个子串可以被转变则第 $i$ 个字符为 'Y'，否则为 'N'。

NOI
6
1 1
1 2
1 3
2 2
2 3
3 3

YNNNYN

样例解释

第$1$个询问对应的字符串为'N'，不需要操作就可以；

第$5$个询问对应的字符串为'OI'，将'O'替换为'NI'，字符变为'NII'，删除'II'，得到'N';

其他子串都不可以。

样例2见文件

数据规模与约定

$30\%$的数据：$|S| \le 100,q\le 100$；

$50\%$的数据：$|S| \le 5000,q\le 5000$；

$100\%$的数据：$1 \le |S| \le 2 \times 10^5 ,1 \le q \le 2 \times 10^5$