String in String

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

inputFormat

outputFormat

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

样例

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

8
9
2
6
2

</p>