字符串

时间限制：$2s$

空间限制：$512MB$

题目描述

我们用 $∣s∣$表示字符串$s$的长度，并用 $s_i$表示字符串$s$中的第$i$个字符。字符串$s$的一个子串，记作 $s_{l,...,r}$（其中 $1≤l≤r≤∣s∣$），指的是由 $r−l+1$个字符 $s_l,s_{l+1},…,s_r$ 拼接而成的字符串。我们说字符串$s$是一个 $k$-倍字符串当且仅当存在一个字符串$t$，使得 s=$t^k$，即 $k$个$t$字符串首尾相连恰好组成$s$。

piggy 想知道，给定字符串$s$和正整数 $x,y$，有多少对正整数$(l,r)$满足 $x≤l≤r≤y$，并且子串$s_{l...r}$可以重新排列成为一个$k$-倍字符串。由于 piggy 喜欢高性能程序，你需要回答 $q$个查询 $(x_1,y_1),(x_2,y_2),…,(x_q,y_q)$。

输入格式

第一行包含三个正整数 n,k,q（$1≤n,k,q≤ 5000$），分别表示字符串的长度、倍数和查询的数量。

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

接下来的 q行每行包含两个正整数 x,y（$1≤x≤y≤n$），表示一个查询。

输出格式

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

样例输入

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

样例输出

2
4
2
0
12
3