时间限制：1000ms　内存限制：512MB

题目描述

市文保所的库房里存着一批碑刻，程老师负责给新收的碑做拓片。碑上的铭文历经风雨，不少段落已经漫漶不清，但有一类纹路保存得意外地好：从某个位置起，沿着碑文正着读过去和倒着读回来，得到的字符序列完全一样。所里的老先生管这种纹路叫"对称纹"，比如碑文片段 aca，从左边读是 a c a，从右边读还是 a c a；再比如 abba，正读倒读都是同一串。单个字符也算——一个字符正读倒读自然是它自己。对称纹是鉴定碑刻年代的重要依据，每段纹路越长，说明当年刻工的章法越讲究。

库房的规定是把每块碑的铭文整理成一行小写字母，按位置从 $1$ 到 $n$ 编号，登记造册。鉴定科的研究员不来库房看原碑，只翻登记册，而且很少整碑通读——他们关心的是某一段连续碑文，比如第 $l$ 到第 $r$ 个字符之间的部分。研究员的问题是固定的：在这段碑文的范围之内，能完整找到的对称纹最长是多少个字符。所谓"完整找到"，指这段对称纹从头到尾都落在第 $l$ 到第 $r$ 个字符之间，一头一尾都不能越出界外；纹路本身必须连续，中间不许跳过字符。

登记册越积越厚，鉴定科的问题也越来越多。同一块碑，上午有人问第 $3$ 到 $18$ 位，下午有人问第 $7$ 到 $42$ 位，每个问题都要尽快答复。靠人眼一段段对着看，遇到长碑文一看就是大半天，所里决定把这项查询工作交给程序处理。

这里把登记的规矩再交代一遍。登记册一旦入册就不再改动——碑文是文物现状的如实记录，缺笔断画都照原样登记，谁也无权添改，所以库房的册子只管查询，从不修订。研究员的每个问题都针对当前册子上的同一段铭文，各问题之间互不影响，先问后问、问多问少，答案都一样。一段对称纹的长短只看字符本身，与它在碑上的位置无关：同样的三个字符，刻在碑首和刻在碑尾，算一样长的纹路。另外，研究员给的范围一定有头有尾，不会出现头在尾后面的倒错范围。

程老师拿到的任务是：给定一块碑整理出的 $n$ 个字符，以及鉴定科提出的 $q$ 个问题，每个问题给出范围 $l, r$，回答第 $l$ 到第 $r$ 个字符之间最长的对称纹有多长。每个问题相互独立，互不干扰；同一范围内可能有好几段一样长的对称纹，只报长度即可，不用指出位置。

输入格式

第一行两个整数 $n, q$，表示碑文长度和询问次数。

第二行一个长度为 $n$ 的字符串，由小写字母组成，表示登记在册的碑文。

接下来 $q$ 行，每行两个整数 $l, r$，表示一次询问的范围。

输出格式

输出 $q$ 行，每行一个整数，依次回答每个询问：范围内最长对称纹的长度。

数据范围

• 特殊性质 A：碑文中所有字符都相同。
• 对于全部数据，$1 \le l \le r \le n$，字符串仅由小写字母组成。

样例

样例 1

输入：

4 3
abba
1 4
1 2
2 3

输出：

4
1
2

解释：第一个问题问整段碑文，abba 整体正读倒读相同，长度 $4$。第二个问题只问前两个字符 ab，其中能完整找到的最长对称纹只有单个字符，长度 $1$。第三个问题问 bb，两个字符相同，正读倒读一致，长度 $2$。

样例 2

输入：

5 2
aacab
1 5
1 2

输出：

3
2

解释：整段 aacab 里，aca 正读倒读相同，长度 $3$；aa 长度 $2$；没有更长的，逐一核对 aaca、acab 等候选都不满足。前两个字符 aa 本身就是一段对称纹，长度 $2$。

样例 3

输入：

5 3
abcba
1 5
2 4
1 3

输出：

5
3
1

解释：整段 abcba 以中间的 c 为轴左右对称，长度 $5$。第 $2$ 到 $4$ 位是 bcb，长度 $3$。前三位 abc 里找不到长度超过 $1$ 的对称纹，单个字符兜底，长度 $1$。