E - リピート再生と部分一致 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は英小文字からなる長さ N の文字列 S で表される曲を持っています。

高橋君の音楽プレイヤーにはリピート再生機能があり、曲が終わると自動的に最初から再び再生されます。これにより、文字列 S を無限に繰り返し連結した文字列 S^{\infty} = SSS\ldots が流れ続けることになります。より正確には、S^{\infty} の第 k 文字目（k = 1, 2, 3, \ldots）は、S の第 ((k - 1) \bmod N) + 1 文字目です。ここで a \bmod b は a を b で割った余りであり、0 以上 b 未満の整数です。

青木君は高橋君に Q 個の質問をします。i 番目の質問では、2つの整数 L_i, R_i（1 \leq L_i \leq R_i）が与えられます。T_i を、S^{\infty} の第 L_i 文字目から第 R_i 文字目までの連続部分文字列とします。T_i の長さは R_i - L_i + 1 です。

各質問に対して、T_i が元の文字列 S の連続部分文字列として出現するかどうかを判定してください。すなわち、1 \leq p かつ p + (R_i - L_i + 1) - 1 \leq N を満たす整数 p が存在して、S の第 p 文字目から第 p + (R_i - L_i + 1) - 1 文字目までの連続部分文字列が T_i と一致するかどうかを判定してください。

なお、T_i の長さ R_i - L_i + 1 が N を超える場合、T_i は長さ N の文字列 S の連続部分文字列にはなりえないため、答えは必ず 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
  • 1 行目には、文字列の長さを表す整数 N と、質問の数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、曲を表す長さ N の文字列 S が与えられる。
  • 続く Q 行にわたって、各質問が与えられる。
  • 2 + i 行目（1 \leq i \leq Q）には、i 番目の質問を表す整数 L_i と R_i がスペース区切りで与えられる。

出力

Q 行出力せよ。i 行目には、i 番目の質問に対して、T_i が S の連続部分文字列として出現するならば Yes を、そうでなければ 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

Score : 466 pts

Problem Statement

Takahashi has a song represented by a string S of length N consisting of lowercase English letters.

Takahashi's music player has a repeat playback feature that automatically replays the song from the beginning when it ends. As a result, the string S infinitely concatenated with itself, S^{\infty} = SSS\ldots, plays continuously. More precisely, the k-th character of S^{\infty} (k = 1, 2, 3, \ldots) is the ((k - 1) \bmod N) + 1-th character of S. Here, a \bmod b is the remainder when a is divided by b, which is an integer at least 0 and less than b.

Aoki asks Takahashi Q questions. In the i-th question, two integers L_i and R_i (1 \leq L_i \leq R_i) are given. Let T_i be the contiguous substring of S^{\infty} from the L_i-th character to the R_i-th character. The length of T_i is R_i - L_i + 1.

For each question, determine whether T_i appears as a contiguous substring of the original string S. That is, determine whether there exists an integer p satisfying 1 \leq p and p + (R_i - L_i + 1) - 1 \leq N such that the contiguous substring of S from the p-th character to the p + (R_i - L_i + 1) - 1-th character matches T_i.

Note that if the length R_i - L_i + 1 of T_i exceeds N, then T_i cannot be a contiguous substring of the string S of length N, so the answer is always No.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • S is a string of length N consisting of lowercase English letters
  • 1 \leq L_i \leq R_i \leq 10^{18}
  • All numerical values given in the input are integers

Input

N Q
S
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • The first line contains an integer N representing the length of the string and an integer Q representing the number of questions, separated by a space.
  • The second line contains the string S of length N representing the song.
  • The following Q lines contain each question.
  • The (2 + i)-th line (1 \leq i \leq Q) contains the integers L_i and R_i representing the i-th question, separated by a space.

Output

Output Q lines. On the i-th line, output Yes if T_i appears as a contiguous substring of S, and No otherwise.

Sample Input 1

5 5
abcab
1 3
4 7
5 6
3 7
11 13

Sample Output 1

Yes
No
No
No
Yes

Sample Input 2

3 4
aab
1 4
4 6
2 4
1 3

Sample Output 2

No
Yes
No
Yes

Sample Input 3

10 8
abracadabr
1 10
11 20
5 14
3 5
1 11
15 18
7 13
100 103

Sample Output 3

Yes
Yes
No
Yes
No
Yes
No
No

Sample Input 4

20 10
abcdeabcdfabcdeabcdf
1 10
11 20
5 16
21 40
1 21
18 23
3 7
100000000000000000 1000000000000000000
35 39
6 10

Sample Output 4

Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes

Sample Input 5

1 3
a
1 1
1000000000000000000 1000000000000000000
999999999999999999 1000000000000000000

Sample Output 5

Yes
Yes
No