该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

可能是字符串签到题

给定一个长度为 $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$。

输入

第一行输入两个整数 $n, q\ (1 \le n, q \le 10^6)$，分别表示字符串长度和查询次数。 第二行输入一个字符串 $s$，仅由小写字母组成。 接下来 $q$ 行，每行两个整数 $l, r\ (1 \le l \le r \le n)$，表示查询子串的下标。

输出

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

样例

5 2
ababa
1 4
4 5

2
1

注释

样例解释： 对于第一组询问，子串 ab 在 abab 中出现了 2 次，没有出现次数更多的子串。