「JZOI-1」拜神

新年快到了，小僖和爸爸妈妈上山拜神，祈求新一年的好气运。

小僖要拜的神一共有 $n$ 个，小僖对每个神的信仰可以用一个小写字母表示，信仰排在一起形成了一个从标号 $1$ 开始的字符串 $s$。 小僖需要祈祷词来拜神，定义一段祈祷词为一个长度大于零的 $s$ 的连续子串，祈祷词的长度为这个子串的长度。由于拜神只需要小僖有着一定的认真度，所以一种祈祷词只要出现两次就可以被称之为有效的。 **注意：只要子串出现的位置开头不同，中间有重复部分也没有问题**。 但是由于还有爸爸妈妈的存在，小僖的祈祷词有时会被干扰而打断，所以只有区间 $[l,r]$ 的字符串（即 $s[l\dots r]$）有效。为了未雨绸缪，小僖将会对可能的情况进行精心准备。 他会给出 $q$ 次询问，每次询问将给定 $l,r$，询问区间 $[l,r]$ 的最长的有效祈祷词的长度。

第一行输入两个正整数 $n,q$。 第二行输入一个由小写字符构成的字符串 $s$。 接下来有 $q$ 行，每行输入两个数 $l,r$。

输出 $q$ 行，每行输出一个非负整数，代表最长的有效祈祷词的长度，若无有效祈祷词，则输出 $0$。

10 5
cdabababdc
3 7
2 8
5 10
6 10
1 4

3
4
2
1
0

#### 样例解释： 对于第一次询问：区间内的字符串为 $\texttt{ababa}$，其中子串 $\texttt{aba}$ 出现了两次，长度为 $3$ 。 对于第二次询问：区间内的字符串为 $\texttt{dababab}$，其中子串 $\texttt{abab}$ 出现了两次，长度为 $4$ 。 对于第三次询问：区间内的字符串为 $\texttt{ababdc}$，其中子串 $\texttt{ab}$ 出现了两次，长度为 $2$ 。 对于第四次询问：区间内的字符串为 $\texttt{babdc}$，其中子串 $\texttt{b}$ 出现了两次，长度为 $1$ 。 对于第五次询问：区间内的字符串为 $\texttt{cdab}$，无出现至少两次的子串，答案为 $0$ 。 #### 数据范围： 对于 $5\%$ 的数据，$n,q\le50$。 对于 $15\%$ 的数据，$n,q\le200$。 对于 $30\%$ 的数据，$n,q\le2\times10^3$。 对于 $40\%$ 的数据，$n,q\le5\times10^3$。 对于 $65\%$ 的数据，$n,q\le2\times 10^4$。 对于另外 $5\%$ 的数据，满足所有的字符都相等。 对于 $100\%$ 的数据，$1 \le n\le5\times10^4$，$1 \le q \le 10^5$。