Problem1345--PIPI的字符串问题Ⅲ

1345: PIPI的字符串问题Ⅲ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 732  Solved: 368
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI双来考查大家字符串处理的能力啦。
给定一个字符串S,以及q次询问。
每次询问给出两个正整数L,R,你需要回答S[L~R]是否为回文串。

Input

第一行给出字符串S,|S|<=1e6. 保证字符串仅由小写字母构成。
第二行给出询问次数q,q<=1e6.
接下来每行给出两个整数L,R,1<=L,R<=|S|.

Output

对于每个询问,若字符串S中[L,R]为回文串,输出YES,否则输出NO。

Sample Input

abccba
5
1 6
2 5
3 4
1 3
1 1

Sample Output

YES
YES
YES
NO
YES

Source/Category

中等