This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them?
给定一个长度为 $n$ 的字符串 $S$，字符集为小写英文字母。
给定 $m$ 个模式串，第 $i$ 个为 $S[\mathrm{tl}_i \cdots \mathrm{tr}_i]$（$S$ 的下标从 $1$ 开始）。
现有 $q$ 次查询，每次给出 $[\mathrm{ql}_i, \mathrm{qr}_i]$，求所有模式串在 $S[\mathrm{ql}_i \cdots \mathrm{qr}_i]$ 中的出现次数之和。
输入格式
第一行为三个整数 $n, m, q$。
第二行为一个长度为 $n$ 的字符串 $S$。
接下来的 $m$ 行，每行两个整数 $\mathrm{tl}_i, \mathrm{tr}_i$。
接下来的 $q$ 行，每行两个整数 $\mathrm{ql}_i, \mathrm{qr}_i$。
输出格式
$q$ 行，每行一个整数，依次表示每个查询的答案。
样例一
input
5 2 2 abaab 3 4 4 5 2 4 1 5
output
1 3
样例二
见附件下载。
数据范围
| 子任务编号 | $n \leqslant $ | $m \leqslant $ | $q \leqslant $ | 特殊性质 | 分值 |
|---|---|---|---|---|---|
| $1$ | $10^3$ | $10^3$ | $10^3$ | 无 | $10$ |
| $2$ | $5 \times 10^4$ | $10^5$ | $5 \times 10^4$ | 无 | $25$ |
| $3$ | $4 \times 10^5$ | $10^6$ | $10^5$ | 保证 $S$ 的所有字符独立地在 b 和 c 中均匀随机生成 |
$20$ |
| $4$ | $4 \times 10^5$ | $10^6$ | $10^5$ | 无 | $45$ |
对于所有数据，$1 \leq n \leq 4 \times 10^5, 1 \leq m \leq 10^6, 1 \leq q \leq 10^5$。
提示
题目不一定按照难度顺序排列。
时间限制：$\texttt{5s}$
空间限制：$\texttt{1GB}$
鄂公网安备 42010202000505 号