美妙世界中的神之字符串

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

用 $|s|$ 表示字符串 $s$ 的长度，用 $s_i$ 表示字符串 $s$ 的第 $i$ 个字符。字符串 $s$ 的子串记为 $s_{l\ldots r}$（$1\le l\le r\le |s|$），它是依次连接 $s_l,s_{l+1},\ldots,s_r$ 得到的字符串。

称字符串 $s$ 为一个 $k$ 重串，当且仅当存在字符串 $t$ 使得 $s=t^k$，即将 $k$ 个 $t$ 首尾相接后恰好得到 $s$。

Aqua 想知道：给定字符串 $s$ 和正整数 $x,y$，有多少对正整数 $l,r$ 满足 $x\le l\le r\le y$，并且子串 $s_{l\ldots r}$ 可以重新排列成一个 $k$ 重串。你需要回答 $q$ 个询问 $(x_1,y_1),(x_2,y_2),\ldots,(x_q,y_q)$。

输入格式

第一行包含三个正整数 $n,k,q$，分别表示字符串长度、询问中的重复次数和询问数量。

第二行包含一个长度为 $n$ 的字符串 $s$，保证 $s$ 只由小写英文字母组成。

接下来 $q$ 行，每行包含两个正整数 $x,y$，表示一个询问。

输出格式

输出 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个询问的答案。

样例输入 1

14 2 6
ssessesessefpq
1 5
1 6
3 6
10 14
1 14
2 7

样例输出 1

2
4
2
0
12
3

样例解释

对于第一个询问，满足条件的二元组 $(l,r)$ 为 $(1,2)$ 和 $(4,5)$。

对于第二个询问，满足条件的二元组 $(l,r)$ 为 $(1,2)$、$(1,6)$、$(3,6)$ 和 $(4,5)$。

数据范围

• $1\le n,k,q\le3\times10^5$；
• $|s|=n$，且 $s$ 只由小写英文字母组成；
• 每个询问满足 $1\le x\le y\le n$。