说明

小 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"}$。

数据规模和约定

本题采用捆绑测试。

对于 $100\%$ 的数据，$1 \le N\le 5\times 10^5$，$1 \le M\le 5 \times 10^5，0\le K \le M$。仅包含小写字母。