「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$ 行每行两个整数。第一个整数指不同的韵脚个数，第二个整数指评分的最大值。

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

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$。仅包含小写字母。