#P17873. [Ontak2019]STR

[Ontak2019]STR

— 字符串重复查询

给定长度为 NN 的小写英文字母字符串 SS。用 [a,b][a,b] 表示从第 aa 个字符到第 bb 个字符组成的子串,下标从1开始。

回答 QQ 次询问,每次给出 l,rl,r,判断是否存在正整数

$$1\le L\le\left\lfloor\frac{r-l+1}{2}\right\rfloor,$$

使下面三个条件至少一个成立:

  1. [l,l+L−1]=[l+L,l+2L−1][l,l+L-1]=[l+L,l+2L-1],即询问子串开头紧挨着两个相同字符串;
  2. [r−L+1,r]=[r−2L+1,r−L][r-L+1,r]=[r-2L+1,r-L],即询问子串末尾紧挨着两个相同字符串;
  3. [l,l+L−1]=[r−L+1,r][l,l+L-1]=[r-L+1,r],即询问子串有两个互不重叠的相同前缀和后缀。

输入格式

第一行两个整数 N,QN,Q。

第二行字符串 SS。接下来 QQ 行,每行两个整数 l,rl,r。

输出格式

每次询问输出一行:存在符合条件的 LL 时输出 YES,否则输出 NO。

数据范围

1≤N,Q≤2000001\le N,Q\le200000,1≤l≤r≤N1\le l\le r\le N。字符串只含小写英文字母。

子任务 附加限制 分值
1 N,Q≤2000N,Q\le2000 10
2 N,Q≤20000N,Q\le20000 30
3 无 60

样例 1

输入:

5 4
abcbc
1 5
1 3
2 4
1 1

输出:

YES
NO
YES
NO