E. God's String on This Wonderful World
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

We use $$$|s|$$$ to denote the length of string $$$s$$$, and $$$s_i$$$ to denote the $$$i$$$-th character of $$$s$$$. A substring of $$$s$$$, denoted $$$s_{l\ldots r}$$$ ($$$1 \le l \le r \le |s|$$$), refers to the string formed by concatenating the $$$r - l + 1$$$ characters $$$s_l, s_{l+1}, \ldots, s_r$$$. We say that $$$s$$$ is a $$$k$$$-fold string if and only if there exists a string $$$t$$$ such that $$$s = t^k$$$, i.e., $$$k$$$ copies of $$$t$$$ concatenated end-to-end exactly form $$$s$$$.

Aqua wants to know, given string $$$s$$$ and positive integers $$$x, y$$$, how many pairs of positive integers $$$l, r$$$ satisfy $$$x \le l \le r \le y$$$ and the substring $$$s_{l\ldots r}$$$ can be rearranged to become a $$$k$$$-fold string. Since Aqua likes high-performance programs, you need to answer $$$q$$$ queries $$$(x_1, y_1), (x_2, y_2), \ldots, (x_q, y_q)$$$.

Input

The first line contains three positive integers $$$n, k, q$$$ ($$$1 \le n, k, q \le 3 \times 10^5$$$), representing the length of the string, the fold count for queries, and the number of queries.

The second line contains a string $$$s$$$ of length $$$n$$$. It is guaranteed that $$$s$$$ consists only of lowercase English letters.

The following $$$q$$$ lines each contain two positive integers $$$x, y$$$ ($$$1 \le x \le y \le n$$$), representing one query per line.

Output

Output $$$q$$$ lines, where the $$$i$$$-th line contains an integer representing the answer to the $$$i$$$-th query.

Example
Input
14 2 6
ssessesessefpq
1 5
1 6
3 6
10 14
1 14
2 7
Output
2
4
2
0
12
3
Note

For the first query, the pairs $$$(l, r)$$$ that satisfy the condition are $$$(1, 2), (4, 5)$$$.

For the second query, the pairs $$$(l, r)$$$ that satisfy the condition are $$$(1, 2), (1, 6), (3, 6), (4, 5)$$$.