10991: K串
[Creator : ]
Description
ZZT 得到了一个字符串 $S$ 以及一个整数 $K$。
WZH 在 1995 年提出了“优雅 K 串”的定义:这个字符串每一种字符的个数都是 $K$ 的倍数。
现在 ZZT 想要对字符串进行 $Q$ 次询问,第 $i$ 次询问给出一个区间 $[L_i, R_i]$,他想计算 $[L_i, R_i]$ 中有多少个子串是“优雅 K 串”。
由于 ZZT 忙于工作,所以他把这个问题交给了你,请你帮忙解决。
Input
第一行输入一个正整数 $K$。
第二行输入一个字符串 $S$。
第三行输入一个正整数 $Q$,表示有 $Q$ 次询问。
接下来 $Q$ 行,每行输入两个正整数 $L_i$ 和 $R_i$,表示第 $i$ 次询问。
Output
每次询问,输出一个正整数,表示满足条件的“优雅 K 串”的数量。
Constraints
$1 ≤ K ≤ 50$
$1≤ | S | ≤ 3 x 10^4$ 且 $S$ 仅包含小写英文字母
$1≤ Q ≤ 3 x 10^4$
$1 ≤ X_i≤ Y_i≤ N$
$1≤ | S | ≤ 3 x 10^4$ 且 $S$ 仅包含小写英文字母
$1≤ Q ≤ 3 x 10^4$
$1 ≤ X_i≤ Y_i≤ N$
Sample 1 Input
1
abc
3
1 3
1 2
2 3
Sample 1 Output
6
3
3