说明

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

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

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

• 令 $f(t)$ 为 $t$ 中任意子串的最大出现频率；
• 令 $|\text{LFS}(t)|$ 为在 $t$ 中恰好出现 $f(t)$ 次的子串的最大长度。

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

若字符串 $x$ 可以通过从 $y$ 的开头删除若干（可能为零或全部）字符以及从结尾删除若干（可能为零或全部）字符得到，则称 $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)$ 的 $|\text{LFS}(s[l, r])|$ 值。

5 4
ababa
1 1
1 5
1 4
2 5

1
1
2
2

10 1
aaaaaaaaaa
1 10

1

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

3
2
3
1
2

提示

样例 1 解释

在第一个样例中：

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

翻译由 DeepSeek 完成