H. 可能是字符串签到题
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$（仅由小写字母组成，下标从 $$$1$$$ 开始），进行 $$$q$$$ 次询问，每次询问给出两个整数 $$$l,r$$$，询问子串 $$$s[l,r]$$$ 中出现次数最多的子串出现了多少次。

注：字符串 $$$s$$$ 的子串定义为 $$$s$$$ 中连续且顺序一致的一段字符序列，即对于下标 $$$l, r$$$ $$$(1 \le l \le r \le |s|)$$$，子串 $$$s[l,r]$$$ 表示为 $$$s_l s_{l+1} \dots s_r$$$。

Input

第一行输入两个整数 $$$n,q(1\le n,q\le 10^6)$$$，分别表示字符串长度和查询次数。

第二行输入一个字符串 $$$s$$$，仅由小写字母组成。

接下来 $$$q$$$ 行，每行两个整数 $$$l,r(1 \le l\le r \le n)$$$，表示查询子串的下标。

Output

对于每个询问，输出一行一个整数，表示出现次数最多的子串出现了多少次。

Example
Input
5 2
ababa
1 4
4 5
Output
2
1
Note

样例解释：

对于第一组询问，子串 $$$\text{ab}$$$ 在 $$$\text{abab}$$$ 中出现了 $$$2$$$ 次，没有出现次数更多的子串。