Poetic Rhyme Scoring

Little C wants to write a poem, but every sentence in his poem must rhyme. A poem is a collection of sentences and the quality of the rhyme is measured by the longest common suffix among the sentences. In this problem, the rhyme score of a set of sentences is defined as the length of their longest common suffix, and the rhyme (or common suffix) is the string (possibly empty) that appears at the end of every sentence in the set.

Initially, Little C has written no sentences. At M moments, he thinks of a sentence and adds it to his memory. Each sentence is given as a substring of a string T of length N. Note that if he generates the same sentence more than once, only one copy is kept.

He believes that once his memory contains more than K sentences, he can write a poem. Therefore, after each new sentence, he asks you to determine two values from the current set of unique sentences: the maximum possible rhyme score and the number of distinct rhyme strings that achieve that maximum score when considering any subset of his sentences with size greater than K. Here, if multiple different subsets yield the same rhyme string, that rhyme is only counted once.

Formally, given any subset S (with |S| > K), let the score be defined as \[ \text{score}(S)=\max\{ |X| : X\ \text{is a suffix of every string in } S \}\] and the corresponding rhyme is the common suffix X of length score(S). Your task is to output, after each sentence is added, the maximum score over all subsets of the current set of unique sentences with size greater than K, and the number of distinct rhyme strings that achieve that score. If no subset with more than K sentences exists, output 0 0.

inputFormat

The first line contains three integers N, M, and K, where N is the length of string T, M is the number of moments (queries), and K is the threshold.

The second line contains the string T.

Each of the following M lines contains two integers L and R (1-indexed), representing the substring T[L...R] that forms a sentence.

outputFormat

After each query, output two space‐separated integers on a new line: the maximum rhyme score (i.e. the length of the longest common suffix) among any subset of unique sentences having more than K elements, and the number of distinct rhyme strings (common suffixes) that achieve this score.

If there is no valid subset (i.e. the number of unique sentences is not greater than K), output 0 0.

sample

10 4 1
abcdefghij
1 3
2 5
3 10
1 3

0 0
0 1
0 1
0 1