# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Limits
1s, 512 MB

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 **i ^{th}** pattern occurs in the

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 <= 10 ^{5}**

**1 <= i <= m <= 50**

**1 <= q <= 10 ^{5}**

**1 <= Length of the pattern <= 10 ^{5}**

For each query you have to tell that how many times the **i ^{th}** string occurs in

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 |

73% Solution Ratio

ZeronfinityEarliest,

rohijulislamFastest, 0.0s

Hasinur_Lightest, 3.2 MB

kzvd4729Shortest, 906B

Login to submit