Problem:


String in String

Problem

文字列SとQ個のクエリが与えられる。

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

Input

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

S Q
l0 r0 M0
l1 r1 M1
.
.
.
lQ&minus;1 rQ&minus;1 MQ&minus;1

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

  続くQ行に整数li, ri, Miが空白区切りで与えられる。

Constraints

1 ≤| S | ≤ 100000

1 ≤ Q ≤ 100000

1 ≤ | Mi | ≤ 100000 (0 ≤ i ≤ Q-1)

0 ≤ li ≤ ri < | 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



Sample input:
rupcrupc 5
0 3 rupc
0 7 rupc
2 7 ru
2 7 pc
1 5 u


Sample output:
1
2
1
2
2

Submission status: Time Limit Exceeded

Solution code:
s, n = input().split()
n = int(n)
for _ in range(n):
    li = input().split()
    # print('li:',li)
    word = li[-1]
    i,j = map(int,li[:2])
    partS = s[i:j+1]
    # print('word:',word)
    # print('parts:',partS)
    nword = 0
    for idx in range(len(partS)-len(word)+1):
        # print(partS[idx:idx+len(word)])
        if partS[idx:idx+len(word)] == word:
            nword += 1
    print(nword)