P5112 FZOUTSY

### Original Meaning cdm1020 is a shut-in. His favorite thing in daily life is chatting (and copying) in group chats. He took the chat logs from a group he recently chatted in, and used some mysterious compression algorithm to compress these chat logs into a string of length $n$. Because he is a chuunibyou-style fan, this string contains only $7$ kinds of characters: $\mathtt{f,z,o,u,t,s,y}$. Because of his obsession with suffix data structures, he is only interested in the suffixes of this string. He defines the index of a suffix to be $i$ if and only if the interval of the string it represents is $[i,n]$. cdm1020 defines a pair of suffixes $(i,j)$ to be “$k$-level copying” if and only if the length of the longest common prefix of suffix $i$ and suffix $j$ is at least $k$. In other words, a pair of $k$-level copying suffixes is also $k-1,k-2,k-3,\cdots,1,0$-level copying. Now he wants to ask: among the suffixes with indices in $(l,r)$, how many pairs of suffixes are $k$-level copying. ### One-Sentence Meaning Given a string of length $n$ over the alphabet $\mathtt{f,z,o,u,t,s,y}$ and a query parameter $k$, for multiple queries $(l,r)$, find among the suffixes with indices in $(l,r)$ how many pairs of suffixes have LCP (longest common prefix) length at least $k$. A suffix has index $i$ if and only if it represents the characters in the interval $(i,n)$.

The first line contains three positive integers $n,m,k$, representing the string length $n$, the number of queries $m$, and the query parameter $k$. The second line contains a string of length $n$, which is the string you need to process. The next $m$ lines each contain two positive integers $l,r$, representing the query interval $l,r$.

Output $m$ lines, each containing a positive integer, representing the number of suffix pairs in the query interval whose LCP length is at least $k$.

### Constraints and Notes For all testdata, $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}$. It is guaranteed that the input string contains only the $7$ lowercase letters $\mathtt{f,z,o,u,t,s,y}$. Translated by ChatGPT 5