Bob 是一位志向远大的先锋派作家。他厌恶使用空格、标点符号、大写字母等；因此，他的故事仅仅是由一长串英文字母小写组成的字符串。评论家们还注意到，他的风格带有某种对重复的偏爱，即有时故事中会出现两个相同的子串连续出现的情况，中间没有任何其他字符。

Bob 提交了他的最新杰作，一个长度为 $n$ 的字符串，给 $q$ 家不同的文学杂志，希望其中至少有一家愿意出版。得到的反响比他预想的要好。所有 $q$ 家杂志的编辑都表示愿意出版他故事的某一部分（即子串），但条件是他必须找出该部分故事中最长的重复（即一个较短的子串连续出现两次）。编辑们打算删除那部分内容，以防止故事过于乏味。现在 Bob 需要你的帮助来回答编辑们的这些询问。

编写一个程序，给定一个包含 $n$ 个字母的字符串 $s[1]s[2] \dots s[n]$，回答 $q$ 个询问。每个询问的形式为：“给定 $a_i$ 和 $b_i$，字符串 $t$ 的最长长度是多少，使得 $tt$ 作为 $s[a_i]s[a_i + 1] \dots s[b_i - 1]s[b_i]$ 的子串出现，并且这种出现的最左侧起始位置在哪里？”

输入格式

第一行包含两个整数 $n$ 和 $q$。第二行包含字符串 $s$，其长度为 $n$；所有字符均为英文字母小写。接下来的 $q$ 行描述询问；第 $i$ 行包含两个由空格分隔的整数 $a_i$ 和 $b_i$。

数据范围

• $1 \le n \le 10^6$
• $1 \le q \le 100$
• 对于每个 $i = 1, 2, \dots, q$，有 $1 \le a_i \le b_i \le n$

输出格式

输出 $q$ 行；第 $i$ 行必须包含两个由空格分隔的整数 $\ell_i$ 和 $c_i$。$\ell_i$ 应为使得 $tt$ 作为 $s[a_i]s[a_i + 1] \dots s[b_i - 1]s[b_i]$ 的子串出现的字符串 $t$ 的最长长度，$c_i$ 应为该长度的最左侧重复开始的索引，即满足 $a_i \le c_i$，$c_i + 2\ell_i - 1 \le b_i$ 且 $s[c_i] \dots s[c_i + \ell_i - 1] = s[c_i + \ell_i] \dots s[c_i + 2\ell_i - 1]$ 的最小整数。（如果 $\ell_i = 0$，则根据定义 $c_i = a_i$。）

样例

输入格式 1

10 4
cabaabaaca
4 8
1 9
5 9
8 10

输出格式 1

1 4
3 2
1 7
0 8

说明

上述示例中的四个询问分别指代子串 aabaa, cabaabaac, abaac 和 aca；加粗部分即为该询问结果所指代的子串（长度为 $\ell_i$，起始索引为 $c_i$）。在最后一个询问中没有重复，因此 $\ell_4 = 0$。