You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

题目描述

小僖要拜的神一共有 $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$。