分数: 466 分
问题陈述
高桥有一首用弦代表的歌 S 长度 N 由小写英文字母组成。
Takahashi 的音乐播放器具有重复播放功能,当歌曲结束时会自动从头开始重播。结果,字符串 S 与其自身无限连接, S^{\infty} = SSS\ldots,连续播放。更准确地说, k- 第一个字符 S^{\infty} (k = 1, 2, 3, \ldots) 是 ((k - 1) \bmod N) + 1- 第一个字符 S。在这里, a \bmod b 是余数 a 除以 b,至少是一个整数 0 且小于 b.
青木问高桥 Q 问题。在 i第题,两个整数 给出了 L_i 和 R_i (1 \leq L_i \leq R_i)。让 T_i 是以下的连续子串 S^{\infty} 来自 L_i- 第一个字符 R_i- 第一个字符。长度为 T_i is R_i - L_i + 1.
对于每个问题,确定是否 T_i 显示为原始字符串的连续子字符串 S。即判断是否存在整数 p 满意 1 \leq p 和 p + (R_i - L_i + 1) - 1 \leq N 这样的连续子串 S 来自 p- 第一个字符 p + (R_i - L_i + 1) - 1- 第一个字符匹配 T_i.
请注意,如果长度 R_i - L_i + 1 of T_i 超过 N,那么 T_i 不能是字符串的连续子字符串 S 长度 N,所以答案总是 No.
约束
- 1 \leq N \leq 5 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- S 是一个长度为的字符串 N 由小写英文字母组成
- 1 \leq L_i \leq R_i \leq 10^{18}
- 输入中给出的所有数值均为整数
输入
N Q S L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 第一行包含一个整数 N 表示字符串的长度和一个整数 Q 代表问题数量,以空格分隔。
- 第二行包含字符串 S 长度 N 代表歌曲。
- 以下 Q 行包含每个问题。
- 的 (2 + i)- 第行 (1 \leq i \leq Q) 包含整数 L_i 和 R_i 代表 i第一个问题,用空格分隔。
输出
输出 Q 行。上 i第行,输出 Yes if T_i 显示为以下内容的连续子字符串 S,和 No 否则。
示例输入 1
5 5 abcab 1 3 4 7 5 6 3 7 11 13
示例输出 1
Yes No No No Yes
示例输入 2
3 4 aab 1 4 4 6 2 4 1 3
示例输出 2
No Yes No Yes
示例输入 3
10 8 abracadabr 1 10 11 20 5 14 3 5 1 11 15 18 7 13 100 103
示例输出 3
Yes Yes No Yes No Yes No No
示例输入 4
20 10 abcdeabcdfabcdeabcdf 1 10 11 20 5 16 21 40 1 21 18 23 3 7 100000000000000000 1000000000000000000 35 39 6 10
示例输出 4
Yes Yes Yes Yes No Yes Yes No Yes Yes
示例输入 5
1 3 a 1 1 1000000000000000000 1000000000000000000 999999999999999999 1000000000000000000
示例输出 5
Yes Yes No