题目描述

原始题意

cdm1020 是一名废宅，他平时最喜欢的事情就是水（复）群（读）。

他截取了他最近水的群的聊天记录，并且通过某种奥妙重重的压缩算法将这些聊天记录压缩成了一个长度为 $n$ 的字符串，因为他是一个中二社厨，所以这个字符串当中仅仅含有 $\mathtt{f,z,o,u,t,s,y}$ 这 $7$ 种字符，出于对后缀数据结构的狂热，他只对这个字符串的后缀感兴趣，他定义一个后缀的编号为 $i$，当且仅当它代表的字符串的区间为 $[i,n]$。

cdm1020 定义一对后缀 $(i,j)$ 是"$k$级复读的"当且仅当 $i$ 和 $j$ 的最长公共前缀的长度大于等于 $k$，换句话说一对$k$级复读的后缀也是 $k-1,k-2,k-3,\cdots,1,0$ 级复读的。

现在他想问你对于编号在 $(l,r)$ 中的后缀，有多少对后缀是 $k$ 级复读的。

一句话题意

给定一个长度为 $n$ 并且字符集为 $\mathtt{f,z,o,u,t,s,y}$ 的字符串和一个询问参数 $k$，多组询问 $(l,r)$ 求编号在 $(l,r)$ 间的后缀中，有多少对后缀的 LCP（最长公共前缀）长度大于等于 $k$。

定义一个后缀的编号为 $i$ 当且仅当这个后缀代表的是 $(i,n)$ 这段区间的字符。

输入格式

第一行三个正整数 $n,m,k$ 分别代表字符串的长度 $n$，询问次数 $m$ 和询问的参数 $k$。

第二行一个长度为 $n$ 的字符串表示你需要处理的字符串。

接下来 $m$ 行，每行两个正整数 $l,r$ 表示询问的区间 $l,r$。

输出格式

输出 $m$ 行正整数，表示询问区间中 LCP 长度大于等于 $k$ 的后缀对数量。

20 15 3
oouuoouuoouuoouuoouu
10 16
2 15
4 13
6 7
4 12
12 14
12 13
7 19
1 5
6 13
1 15
9 15
11 15
1 19
15 18

3
18
8
0
6
0
0
12
1
4
21
3
1
32
0

提示

数据范围及约定

对于全部数据，$1\leq l\leq r\leq n \leq 3×10^6$，$1\leq k \leq n \leq 3×10^6$，$1\leq m \leq 10^5$，$1 \leq n^2m \leq 10^{15}$。

保证输入的字符串中仅含 $\mathtt{f,z,o,u,t,s,y}$ 这 $7$ 种小写字母。