将众所周知的算法进行推广，使其变得不再那么平凡，这总是很酷的！

给定一个字符串 $S$。你的任务是处理 $q$ 个所谓的 $\pi$-查询。每个 $\pi$-查询由两个整数参数 $l$ 和 $r$ ($1 \le l \le r \le |S|$) 确定。$\pi$-查询的答案是满足 $S[l \dots l + x - 1] = S[r - x + 1 \dots r]$ 的最大非负整数 $x \le r - l$（所有区间均为闭区间，索引从 1 开始）。注意，$x = 0$ 总是满足给定条件，因为等式两边都是空字符串。

例如，对于字符串 $S = \text{“gabacababad”}$，$l = 2$ 且 $r = 8$ 的 $\pi$-查询结果为 $3$，因为 $S[2 \dots 4] = S[6 \dots 8] = \text{“aba”}$，且没有更大的值满足上述条件。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 2 \cdot 10^5$)，分别表示字符串 $S$ 的长度和查询次数。

第二行包含由 $n$ 个小写英文字母组成的字符串 $S$。

接下来的 $q$ 行，每行包含两个正整数 $l_i, r_i$ ($1 \le l_i \le r_i \le n$)，描述第 $i$ 个 $\pi$-查询。

输出格式

按输入顺序输出每个查询的答案。

样例

样例输入 1

11 3
gabacababad
2 8
1 3
6 10

样例输出 1

3
0
3