Suffix LCP Pairs

Given a string s of length \(n\) consisting only of the seven characters \(\mathtt{f, z, o, u, t, s, y}\), and an integer parameter \(k\), we define the suffix starting at position \(i\) (1-indexed) as the substring \(s[i \ldots n]\). For any two suffixes \(i\) and \(j\), their Longest Common Prefix (LCP) is the largest \(\ell\) such that \(s[i \ldots i+\ell-1] = s[j \ldots j+\ell-1]\). We say that the pair of suffixes \((i,j)\) is a \(k\)-level repeat if their LCP has length at least \(k\) (note that such a pair is automatically a \(t\)-level repeat for all \(t \le k\)).

You are given multiple queries. Each query provides two integers \(l\) and \(r\): consider all suffixes whose starting positions are in the range \([l, r]\) (1-indexed), and count the number of unordered pairs \((i,j)\) with \(l \le i < j \le r\) that are \(k\)-level repeats.

inputFormat

The first line contains three integers \(n\), \(k\), and \(q\) where \(n\) is the length of the string, \(k\) is the threshold for the LCP, and \(q\) is the number of queries.

The second line contains a string \(s\) of length \(n\) consisting only of characters from the set {\(f, z, o, u, t, s, y\)}.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) (1-indexed) representing a query.

outputFormat

For each query, output a single integer on a new line representing the number of pairs of suffixes (with starting positions in the range \([l, r]\)) whose longest common prefix has length at least \(k\).

sample

6 2 2
fzfzfz
1 6
2 4

4
1