Problem

Given the strings S and Q queries.
The i-th query (0 ≤ i ≤ Q-1) is given the closed interval [li, ri] and the string Mi. Output how many character strings Mi exist in the substring from the li character to the ri character of S.

Constraints

• 1 ≤ | S | ≤ 100000
• 1 ≤ Q ≤ 100000
• 1 ≤ | Mi | ≤ 100000 (0 ≤ i ≤ Q-1)
• 0 ≤ li ≤ ri <| S | (0 ≤ i ≤ Q-1)
• All characters are lowercase
• The total number of characters in string M does not exceed 2000000

Input

The input is given in the following format.

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

The string S and the number of queries Q are given on the first line, separated by blanks.
The following Q lines are given the integers li, ri, Mi, separated by blanks.

Output

The output consists of Q lines. Print the answer to each query on one line in turn.

Examples

Input

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

Output

1
2
1
2
2

Input

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

Output

4
3
0
2
1
2
1
2

Input

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

Output

8
9
2
6
2

见题面

见题面