This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them?
Given a string $S$ of length $n$ consisting of lowercase English letters.
Given $m$ pattern strings, where the $i$-th pattern is $S[\mathrm{tl}_i \cdots \mathrm{tr}_i]$ (using 1-based indexing for $S$).
There are $q$ queries. Each query provides a range $[\mathrm{ql}_i, \mathrm{qr}_i]$, and you need to calculate the total number of occurrences of all pattern strings within $S[\mathrm{ql}_i \cdots \mathrm{qr}_i]$.
Input
The first line contains three integers $n, m, q$.
The second line contains a string $S$ of length $n$.
The next $m$ lines each contain two integers $\mathrm{tl}_i, \mathrm{tr}_i$.
The next $q$ lines each contain two integers $\mathrm{ql}_i, \mathrm{qr}_i$.
Output
Output $q$ lines, each containing an integer representing the answer to the corresponding query.
Examples
Input 1
5 2 2 abaab 3 4 4 5 2 4 1 5
Output 1
1 3
Input 2
See attachment.
Constraints
| Subtask ID | $n \leqslant $ | $m \leqslant $ | $q \leqslant $ | Special Properties | Score |
|---|---|---|---|---|---|
| $1$ | $10^3$ | $10^3$ | $10^3$ | None | $10$ |
| $2$ | $5 \times 10^4$ | $10^5$ | $5 \times 10^4$ | $25$ | |
| $3$ | $4 \times 10^5$ | $10^6$ | $10^5$ | $S$ is guaranteed to be generated by picking characters independently and uniformly from {'b', 'c'} | $20$ |
| $4$ | None | $45$ |
For all data, $1 \leq n \leq 4 \times 10^5, 1 \leq m \leq 10^6, 1 \leq q \leq 10^5$.
Note
The problems are not necessarily ordered by difficulty.