你正在设计一款新的电子游戏《Live Fight Simulator》。关卡由一个长度为 $n$ 的由小写英文字母组成的字符串 $s$ 定义，其中每个字母代表依次出现的一种敌人类型。

为了分析游戏平衡性，你需要衡量关卡不同部分的重复程度。你将考虑关卡中 $q$ 个特定的连续子串 $s[l, r]$，其中 $1 \le l \le r \le n$。

对于每个询问，你想计算 LFS（最长频繁子串，Longest Frequent Substring）的长度。形式化地，对于任意字符串 $t$：

• 令 $f(t)$ 为 $t$ 中任意子串的最大出现次数；
• 令 $|LFS(t)|$ 为 $t$ 中恰好出现 $f(t)$ 次的子串的最大长度。

对于每个询问 $(l, r)$，你必须计算 $|LFS(s[l, r])|$，它表示该关卡部分中重复次数最多的敌人生成模式的最大长度。

如果可以通过从字符串 $y$ 的开头删除若干个（可能是零个或全部）字符以及从末尾删除若干个（可能是零个或全部）字符来获得字符串 $x$，则称字符串 $x$ 是字符串 $y$ 的子串。

输入格式

第一行包含两个整数 $n, q$ ($1 \le n \le 5 \cdot 10^5$, $1 \le q \le 5 \cdot 10^5$) —— 序列的长度和要分析的关卡片段数量。

第二行包含一个长度为 $n$ 的由小写英文字母组成的字符串 $s$。

接下来的 $q$ 行，每行包含两个整数 $l, r$ ($1 \le l \le r \le n$)，表示对子串 $s[l, r]$ 的一次询问。

输出格式

输出 $q$ 行。第 $i$ 行必须包含一个整数：双元组 $(l, r)$ 对应的 $|LFS(s[l, r])|$ 的值。

样例

输入 1

5 4
ababa
1 1
1 5
1 4
2 5

输出 1

1
1
2
2

输入 2

10 1
aaaaaaaaaa
1 10

输出 2

1

输入 3

17 5
deabcabcabdeadede
1 8
1 10
4 9
2 16
1 17

输出 3

3
2
3
1
2

说明

样例 1 说明。在第一个样例中：

• 在第一个询问中，子串为 $t = s[1, 1] = \text{"a"}$。$t$ 内部子串的最大出现次数为 $1$，由 $\text{"a"}$ 本身达到，其长度为 $1$。因此，答案为 $1$。
• 在第二个询问中，子串为 $t = s[1, 5] = \text{"ababa"}$。$t$ 内部子串的最大出现次数为 $3$，由 $\text{"a"}$ 达到，其长度为 $1$。因此，答案为 $1$。
• 在第三个询问中，子串为 $t = s[1, 4] = \text{"abab"}$。$t$ 内部子串的最大出现次数为 $2$，由 $\text{"a"}$、$\text{"b"}$ 和 $\text{"ab"}$ 达到。在这些字符串中，长度最大的是 $\text{"ab"}$，其长度为 $2$。因此，答案为 $2$。
• 在第四个询问中，子串为 $t = s[2, 5] = \text{"baba"}$。$t$ 内部子串的最大出现次数为 $2$，由 $\text{"a"}$、$\text{"b"}$ 和 $\text{"ba"}$ 达到。在这些字符串中，长度最大的是 $\text{"ba"}$，其长度为 $2$。因此，答案为 $2$。