String in String

Problem

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

Input

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

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

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

Constraints

• 1 ≤| S | ≤ 100000
• 1 ≤ Q ≤ 100000
• 1 ≤ | M_i | ≤ 100000 (0 ≤ i ≤ Q-1)
• 0 ≤ l_i ≤ r_i < | S | (0 ≤ i ≤ Q-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