E - Lexicographic Ranking of Circular Strings Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

N 個の石が円形に並んでいます。石には時計回りに 1 から N までの番号が付いており、石 i には英小文字 S_i が刻まれています。石 N の時計回りの次は石 1 です。

開始位置 x（1 \leq x \leq N）と長さ \ell（1 \leq \ell \leq N）に対して、文字列 C(x, \ell) を次のように定義します。

  • C(x, \ell)：石 x から時計回りに \ell 個の石を順に読んで得られる長さ \ell の文字列。

すなわち、C(x, \ell) の k 文字目（1 \leq k \leq \ell）は石 ((x + k - 2) \bmod N) + 1 に刻まれた文字です。

高橋君の現在位置を変数 P で表します。P の初期値は 1 です。

Q 個のクエリが順に与えられます。i 番目のクエリでは整数 A_i と L_i が与えられ、以下の操作を行います。

  1. 移動：現在位置 P を時計回りに A_i 個先の石に更新します。すなわち、

    P \leftarrow ((P + A_i - 1) \bmod N) + 1

    とします（A_i = 0 のときは P は変化しません）。

  2. 数え上げ：次の値を求めて出力します。

    \#\{\, (x, \ell) \mid 1 \leq x \leq N,\ 1 \leq \ell \leq L_i,\ C(x, \ell) < C(P, \ell) \,\}

ここで、C(x, \ell) < C(P, \ell) は長さ \ell の文字列同士の辞書順比較を意味し、辞書順は英小文字の通常の順序 \mathrm{a} < \mathrm{b} < \cdots < \mathrm{z} に従います。

言い換えると、開始位置 x（1 \leq x \leq N）と長さ \ell（1 \leq \ell \leq L_i）のすべての組 (x, \ell) のうち、C(x, \ell) が C(P, \ell) よりも辞書順で厳密に小さいものの個数を求めてください。

制約

  • 1 \leq N \leq 3000
  • 1 \leq Q \leq 10^5
  • S は長さ N の英小文字からなる文字列
  • 0 \leq A_i \leq N - 1（1 \leq i \leq Q）
  • 1 \leq L_i \leq N（1 \leq i \leq Q）
  • 入力はすべて整数（S を除く）

入力

N Q
S
A_1 L_1
A_2 L_2
\vdots
A_Q L_Q
  • 1 行目には、石の個数 N とクエリの個数 Q がスペース区切りで与えられる。
  • 2 行目には、長さ N の英小文字列 S が与えられる。S の i 文字目 S_i は石 i に刻まれている文字を表す。
  • 2 + i 行目（1 \leq i \leq Q）には、i 番目のクエリにおける移動量 A_i と長さの上限 L_i がスペース区切りで与えられる。

出力

Q 行出力してください。

i 行目には、i 番目のクエリに対する答えを整数で出力してください。

入力例 1

5 4
abaca
0 1
1 3
3 5
4 2

出力例 1

0
9
0
8

入力例 2

4 5
aaaa
0 1
1 2
2 3
3 4
0 4

出力例 2

0
0
0
0
0

入力例 3

12 8
bananaabcxyz
0 6
5 4
11 12
3 7
8 2
1 10
10 11
6 5

出力例 3

24
0
84
34
2
70
86
30

入力例 4

30 15
qwertyuiopasdfghjklzxcvbnmabcd
0 1
29 30
15 10
7 25
3 3
28 30
14 1
1 29
20 15
5 30
0 12
11 20
27 7
6 18
2 30

出力例 4

20
209
100
124
51
750
24
348
30
240
96
180
6
234
450

入力例 5

1 5
z
0 1
0 1
0 1
0 1
0 1

出力例 5

0
0
0
0
0

Score : 466 pts

Problem Statement

N stones are arranged in a circle. The stones are numbered from 1 to N in clockwise order, and stone i has the lowercase English letter S_i engraved on it. The next stone clockwise from stone N is stone 1.

For a starting position x (1 \leq x \leq N) and a length \ell (1 \leq \ell \leq N), define the string C(x, \ell) as follows:

  • C(x, \ell): The string of length \ell obtained by reading \ell stones consecutively in clockwise order starting from stone x.

That is, the k-th character (1 \leq k \leq \ell) of C(x, \ell) is the character engraved on stone ((x + k - 2) \bmod N) + 1.

Takahashi's current position is represented by a variable P. The initial value of P is 1.

Q queries are given in order. In the i-th query, integers A_i and L_i are given, and the following operations are performed:

  1. Move: Update the current position P to the stone A_i positions ahead in the clockwise direction. That is,

    P \leftarrow ((P + A_i - 1) \bmod N) + 1

    (When A_i = 0, P does not change.)

  2. Count: Compute and output the following value:

    \#\{\, (x, \ell) \mid 1 \leq x \leq N,\ 1 \leq \ell \leq L_i,\ C(x, \ell) < C(P, \ell) \,\}

Here, C(x, \ell) < C(P, \ell) denotes lexicographic comparison between strings of length \ell, where the lexicographic order follows the usual ordering of lowercase English letters \mathrm{a} < \mathrm{b} < \cdots < \mathrm{z}.

In other words, among all pairs (x, \ell) with starting position x (1 \leq x \leq N) and length \ell (1 \leq \ell \leq L_i), count the number of pairs for which C(x, \ell) is strictly lexicographically smaller than C(P, \ell).

Constraints

  • 1 \leq N \leq 3000
  • 1 \leq Q \leq 10^5
  • S is a string of length N consisting of lowercase English letters
  • 0 \leq A_i \leq N - 1 (1 \leq i \leq Q)
  • 1 \leq L_i \leq N (1 \leq i \leq Q)
  • All inputs are integers (except for S)

Input

N Q
S
A_1 L_1
A_2 L_2
\vdots
A_Q L_Q
  • The first line contains the number of stones N and the number of queries Q, separated by a space.
  • The second line contains a lowercase English string S of length N. The i-th character S_i of S represents the character engraved on stone i.
  • The (2 + i)-th line (1 \leq i \leq Q) contains the movement amount A_i and the upper bound on length L_i for the i-th query, separated by a space.

Output

Output Q lines.

On the i-th line, output the answer to the i-th query as an integer.

Sample Input 1

5 4
abaca
0 1
1 3
3 5
4 2

Sample Output 1

0
9
0
8

Sample Input 2

4 5
aaaa
0 1
1 2
2 3
3 4
0 4

Sample Output 2

0
0
0
0
0

Sample Input 3

12 8
bananaabcxyz
0 6
5 4
11 12
3 7
8 2
1 10
10 11
6 5

Sample Output 3

24
0
84
34
2
70
86
30

Sample Input 4

30 15
qwertyuiopasdfghjklzxcvbnmabcd
0 1
29 30
15 10
7 25
3 3
28 30
14 1
1 29
20 15
5 30
0 12
11 20
27 7
6 18
2 30

Sample Output 4

20
209
100
124
51
750
24
348
30
240
96
180
6
234
450

Sample Input 5

1 5
z
0 1
0 1
0 1
0 1
0 1

Sample Output 5

0
0
0
0
0