Description

Little C wants to write a poem, but writing poetry requires rhyming.

A poem is made up of many sentences, and these sentences need to rhyme.

However, rhyming can be good or bad. Little C has a score for rhyming. The score is defined as the length of the longest common suffix of these sentences, and the rhyme ending is defined as a common suffix of these sentences. A rhyme ending can be the empty string, and a set can have multiple rhyme endings.

At the beginning, Little C has not written a single sentence. That is, the initial memory set is empty.

Little C will think at $M$ moments. At each moment, he comes up with one sentence, i.e., he adds a new sentence to the memory set.

Little C may add multiple identical sentences; please keep only one. Since his memory is very good, the sentences he thinks of will not be forgotten.

But he does not want to spend too much effort making sentences, so he believes that as long as there are more than $K$ sentences, a poem can be formed. Therefore, after thinking of each sentence, he asks you for the maximum score among all subsets of the set whose size is $> K$, and the number of distinct types of rhyme endings of all subsets of the set whose size is $> K$. Note: if multiple different qualifying subsets have the same rhyme ending, then this rhyme ending is counted only once.

Since Little C is very strong, the total length of all sentences he creates may be very large. To make it easier to tell you these sentences, every sentence he creates is a substring of a master string $T$ of length $N$.

Note: The set is required to have uniqueness, i.e., the elements in the set should be pairwise distinct. If there are duplicate elements, keep only one.

Input Format

The first line contains three integers $N, M, K$.

The second line contains a string of length $N$, which is the master string $T$.

The next $M$ lines each contain two integers $l, r$, indicating that at the current moment, the sentence Little C thinks of is the substring $[l, r]$ of the master string.

Output Format

Output $M$ lines, each containing two integers. The first integer is the number of distinct rhyme endings, and the second integer is the maximum score.

5 5 1
ababa
1 2
2 3
1 3
1 4
2 5

0 0
1 0
3 2
5 2
6 3

Hint

Sample Explanation

After the first moment, the memory set is $\{\texttt{"ab"}\}$. No subset satisfies the condition, output $0\ 0$.

After the second moment, the memory set is $\{\texttt{"ab","ba"}\}$. The only rhyme ending that can be obtained is the empty string.

After the third moment, the memory set is $\{\texttt{"ab","ba","aba"}\}$. The rhyme endings that can be obtained are the empty string, $\texttt{"a"}$, $\texttt{"ba"}$.

After the fourth moment, the memory set is $\{\texttt{"ab","ba","aba","abab"}\}$. The rhyme endings that can be obtained are the empty string, $\texttt{"a"}$, $\texttt{"ba"}$, $\texttt{"b"}$, $\texttt{"ab"}$.

After the fifth moment, the memory set is $\{\texttt{"ab","ba","aba","abab","baba"}\}$. The rhyme endings that can be obtained are the empty string, $\texttt{"a"}$, $\texttt{"ba"}$, $\texttt{"b"}$, $\texttt{"ab"}$, $\texttt{"aba"}$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the data, $1 \le N\le 5\times 10^5$, $1 \le M\le 5 \times 10^5$, $0\le K \le M$. The string contains only lowercase letters.

Translated by ChatGPT 5