L : String in String

Time Limit : 2 sec, Memory Limit : 524288 KB

Problem L: 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

一行ごとに各クエリに対する答えを出力せよ

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