String in String

Time Limit : 2 sec, Memory Limit : 524288 KB

String in String

Problem

文字列SQ個のクエリが与えられる。
i番目のクエリ(0 ≤ iQ-1)には閉区間[li,ri]と文字列Miが与えられる。 Sli文字目からri文字目までの部分文字列の中に文字列Miはいくつ存在するか出力せよ。

Input

入力は以下の形式で与えられる。

S Q
l0 r0 M0
l1 r1 M1
.
.
.
lQ−1 rQ−1 MQ−1

1行目に文字列Sとクエリの数Qが空白区切りで与えられる。
続くQ行に整数li, ri, Miが空白区切りで与えられる。

Constraints

  • 1 ≤| S | ≤ 100000
  • 1 ≤ Q ≤ 100000
  • 1 ≤ | Mi | ≤ 100000 (0 ≤ iQ-1)
  • 0 ≤ liri < | S | (0 ≤ iQ-1)
  • 文字はすべて英小文字である
  • 文字列Mの合計文字数は2000000を越えない

Output

出力はQ行からなる。各クエリに対する答えを順番に1行に出力せよ。

Sample Input 1

rupcrupc 5
0 3 rupc
0 7 rupc
2 7 ru
2 7 pc
1 5 u

Sample Output 1

1
2
1
2
2

Sample Input 2

abatagaadbura 8
0 6 a
6 12 a
0 6 aa
0 3 a
3 5 a
5 9 a
1 8 b
1 12 b

Sample Output 2

4
3
0
2
1
2
1
2

Sample Input 3

aaaaaaaaaa 5
0 9 aaa
0 9 aa
5 9 aaaa
2 8 aa
1 2 a

Sample Output 3

8
9
2
6
2

Source: Ritsumeikan University Competitive Programming Camp 2016 Day2 , Japan, 2016-03-07