「MCOI-03」诗韵

题目背景

$\texttt{And the game was over and the player woke up from the dream. }$ 游戏结束了,玩家从梦中醒来。 $\texttt{And the player began a new dream. }$ 并开始了新的梦境。 $\texttt{And the player dreamed again, dreamed better.}$ 并再次沉入梦境中,沉入更好的梦。 $\texttt{And the player was the universe. And the player was love.}$ 而玩家就是宇宙。而玩家就是爱。 $\texttt{You are the player.}$ 你就是那个玩家。 $\texttt{Wake up.}$ 该醒了。

题目描述

小 C 想要写首诗文,但是写诗需要押韵。 一首诗文是由需多句子组成,这些句子需要押韵。 但押韵也有优劣。小 C 对押韵有一个评分。评分定义为这些句子的最长公共后缀长度,而韵脚被定义为这些句子的公共后缀。韵脚可以为空串,一个集合的韵脚可以有多个。 最开始,小 C 一个句子也没有写出来。即最开始的记忆集合为空。 小 C 会思考 $M$ 个时刻。每个时刻,他会想出一个句子。即向记忆集合中加入一个新的句子。 小 C 可能会加入多个相同的句子,请只保留一个。因为他的记忆力很好,所以他想到的句子不会被遗忘。 但是他不想花太多心思去造句,所以他认为,只要有 **大于** $K$ 个句子,就能写成一首诗。所以每想出一个句子后,他会向你询问集合所有的元素个数 $>K$ 的子集的评分的最大值,和集合所有元素个数 $>K$ 的子集的韵脚的种类。注意:如果有多个不同的满足条件的集合韵脚相同,则这个韵脚只能计算一次。 由于小 C 很强,所以他造的所有句子的总长度可能非常大。为了方便告诉你这些句子,他造的每一个句子都是长度为 $N$ 的母串 $T$ 的子串。 **注意**:集合是满足特异性的,即集合中的元素应该互不相同,如果有相同元素仅保留一个。

输入输出格式

输入格式


第一行包括三个整数 $N,M,K$。 第二行包括一个长度为 $N$ 的字符串,即母串 $T$。 接下来 $M$ 行,每行两个整数 $l,r$,表示当前时刻 小C 想起的句子是母串的 $[l,r]$ 子串。

输出格式


$M$ 行每行两个整数。第一个整数指不同的韵脚个数,第二个整数指评分的最大值。

输入输出样例

输入样例 #1

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

输出样例 #1

0 0
1 0
3 2
5 2
6 3

说明

#### 样例解释 第一个时刻后,记忆集合为 $\{\texttt{"ab"}\}$。没有子集满足条件,输出 $0\ 0$。 第二个时刻后,记忆集合为 $\{\texttt{"ab","ba"}\}$。能得到的韵脚只有空串。 第三个时刻后,记忆集合为 $\{\texttt{"ab","ba","aba"}\}$。能得到的韵脚有空串,$\texttt{"a"}$,$\texttt{"ba"}$。 第四个时刻后,记忆集合为 $\{\texttt{"ab","ba","aba","abab"}\}$。能得到的韵脚有空串,$\texttt{"a"}$,$\texttt{"ba"}$,$\texttt{"b"}$,$\texttt{"ab"}$。 第五个时刻后,记忆集合为 $\{\texttt{"ab","ba","aba","abab","baba"}\}$。能得到的韵脚有空串,$\texttt{"a"}$,$\texttt{"ba"}$,$\texttt{"b"}$,$\texttt{"ab"}$,$\texttt{"aba"}$。 #### 数据规模和约定 **本题采用捆绑测试。** | 子任务编号 | $N\le$ | $M\le$ | 时限 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $10$ | $\rm1s$ | $15$ | | $2$ | $ 10^3$ | $10^3$ | $\rm 1s$ | $20$ | | $3$ | $10^5$ | $10^5$ | $\rm 1s$ | $25$ | | $4$ | $ 5\times 10^5$ | $5\times 10^5$ | $\rm 2.33s$ | $40$ | 对于 $100\%$ 的数据,$1 \le N\le 5\times 10^5$,$1 \le M\le 5 \times 10^5,0\le K \le M$。仅包含小写字母。