← 返回题目列表

AtCoder · awc0047_e

E. 重复播放和部分匹配

中文机器翻译题面 查看原题

分数: 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