This year again Intra KUET programming contest is happening . Many participants registered for this exciting contest. Harry Potter is one of them. For this purpose he is practicing day and night to become the champion in this contest. But he is very weak at string related problems. On the other hand his friend Ron is expert in many string related problems. So Ron wanted to help his friend to overcome the fear of strings . He gave Harry Potter a String X and a pattern Y. He told Harry Potter to find how many times Y occurs in X. But this is very easy to solve and Harry Potter will not learn anything from this. To make the problem more interesting Ron told him that he will give M patterns and some query. For each query he is given a range [l, r] which denotes the index of the X string . He has to tell that how many times the ith pattern occurs in the X string in that range.
Input
The first line contains a string X with length N consisting of lowercase English letters.
The second line contains an integer M and Q. M is the number of patterns and Q is the number of queries . The M following lines will contain the i’th pattern . Then the q following lines will contain three integer i, l, r.
1 <= l <= r <= n <= 105
1 <= i <= m <= 50
1 <= q <= 105
1 <= Length of the pattern <= 105
Output
For each query you have to tell that how many times the ith string occurs in X string in that range [l, r].
Sample
| Input | Output |
|---|---|
abababa 3 5 ab ba aba 1 1 4 1 2 7 2 1 6 3 4 7 2 3 5 | 2 2 2 1 1 |
