The talented Little A has been selected as the problem setter for ION2018, and now he needs to solve the problem of naming the tasks.
Little A has been selected as the problem setter for ION2018. He has meticulously prepared a high-quality problem and has completed all tasks except for naming it.
Since the ION has been held for many years, there are regulations regarding problem naming. The ION problem-setting manual states: Every year, the problem-setting committee specifies a lowercase string, which we call that year's "naming string." The name of every problem must be a non-empty contiguous substring of that year's naming string, and it cannot be the same as the name of any problem from the previous year.
Due to some special reasons, Little A does not know the names of the problems from ION2017, but he has obtained the naming string for ION2017 through some special means. Now, Little A has $Q$ queries: for each query, given the naming string for ION2017 and the naming string for ION2018, find the number of ways to name a problem such that the name satisfies the committee's regulations—that is, it is a non-empty contiguous substring of the ION2018 naming string and is definitely not the same as the name of any problem from ION2017.
For some special reasons, all ION2017 naming strings provided in the queries are contiguous substrings of a certain string; see the Input section for details.
Input
The first line contains a string $S$. All ION2017 naming strings provided in the subsequent queries are contiguous substrings of $S$. The second line contains a positive integer $Q$, representing the number of queries. The next $Q$ lines each contain a string $T$ and two positive integers $l, r$, representing a query where the ION2017 naming string is $S[l..r]$ and the ION2018 naming string is $T$. Find the number of naming methods that satisfy the regulations.
It is guaranteed that all strings provided in the input consist of lowercase English letters.
Output
Output $Q$ lines, where the $i$-th line contains a non-negative integer representing the answer to the $i$-th query.
Examples
Input 1
scbamgepe 3 smape 2 7 sbape 3 8 sgepe 1 9
Output 1
12 10 4
Input 2
(See name/name2.in in the contestant directory)
Output 2
(See name/name2.ans in the contestant directory)
Subtasks
| Test Case | $ | S | \le$ | $Q \le$ | $\sum | T | \le$ | Query Constraints | Other Constraints |
|---|---|---|---|---|---|---|---|---|---|
| 1 | $200$ | $200$ | $40000$ | For all queries, $l=1, r= | S | $ | $ | T | \le 200$ |
| 2 | $1000$ | $200$ | $40000$ | For all queries, $l=1, r= | S | $ | $ | T | \le 200$ |
| 3 | $5 \times 10^5$ | $200$ | $5 \times 10^5$ | None | None | ||||
| 4 | $5 \times 10^5$ | $200$ | $5 \times 10^5$ | None | None | ||||
| 5 | $5 \times 10^5$ | $200$ | $5 \times 10^5$ | None | None | ||||
| 6 | $5 \times 10^5$ | $1$ | $5 \times 10^5$ | None | None | ||||
| 7 | $5 \times 10^5$ | $1$ | $5 \times 10^5$ | None | None | ||||
| 8 | $10^5$ | $10^5$ | $2 \times 10^5$ | None | Random string | ||||
| 9 | $10^5$ | $10^5$ | $2 \times 10^5$ | None | Random string | ||||
| 10 | $2 \times 10^5$ | $10^5$ | $4 \times 10^5$ | None | None | ||||
| 11 | $2 \times 10^5$ | $10^5$ | $4 \times 10^5$ | None | Random string | ||||
| 12 | $3 \times 10^5$ | $10^5$ | $6 \times 10^5$ | None | None | ||||
| 13 | $3 \times 10^5$ | $10^5$ | $6 \times 10^5$ | None | Random string | ||||
| 14 | $4 \times 10^5$ | $10^5$ | $8 \times 10^5$ | None | None | ||||
| 15 | $4 \times 10^5$ | $10^5$ | $8 \times 10^5$ | None | Random string | ||||
| 16 | $5 \times 10^5$ | $10^5$ | $10^6$ | None | None | ||||
| 17 | $5 \times 10^5$ | $10^5$ | $10^6$ | None | Random string | ||||
| 18 | $2 \times 10^5$ | $10^5$ | $10^6$ | None | None | ||||
| 19 | $3 \times 10^5$ | $10^5$ | $10^6$ | None | None | ||||
| 20 | $4 \times 10^5$ | $10^5$ | $10^6$ | None | None | ||||
| 21 | $5 \times 10^5$ | $10^5$ | $10^6$ | None | None | ||||
| 22 | $5 \times 10^5$ | $10^5$ | $10^6$ | None | None | ||||
| 23 | $5 \times 10^5$ | $10^5$ | $10^6$ | None | None | ||||
| 24 | $5 \times 10^5$ | $10^5$ | $10^6$ | None | None | ||||
| 25 | $5 \times 10^5$ | $10^5$ | $10^6$ | None | None |
For all data, it is guaranteed that $1 \le l \le r \le |S|$ and $1 \le |T| \le 5 \times 10^5$.