题目描述

考虑一个只由字符 A、B、C 组成的字符串 $t$。对于该字符串，可以进行如下操作：

• 任意选择一个子串 $t[l:r]$，以及字符 $($A$,$B$,$C$)$ 的任意一种排列 $(X, Y, Z)$。这里，$t[l:r]$ 表示从第 $l$ 个字符到第 $r$ 个字符组成的子串，$l$ 和 $r$ 可以任意选择。然后，将 $t[l:r]$ 中的每个 A 替换为 $X$，每个 B 替换为 $Y$，每个 C 替换为 $Z$。

例如，对于字符串 $t =$ ACBAAC，可以选择子串 $t[3:6]$ 和排列 $(X, Y, Z) = ($C$,$B$,$A$)$。执行该操作后，字符串变为 ACBCCA。

阿丽娜喜欢所有字符都相同的字符串。她将字符串 $t$ 的“美丽度”定义为：将其所有字符变为相同所需的最少操作次数。

给定一个长度为 $N$、只包含字符 A、B、C 的字符串 $S$。请回答 $Q$ 个询问。第 $i$ 个询问如下：

• 给定整数 $L_i$ 和 $R_i$，请你求出子串 $t = S[L_i:R_i]$ 的美丽度。

输入格式

输入从标准输入按以下格式给出。

$N$ $Q$ $S$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$

输出格式

输出共 $Q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

样例 1

输入

6 4
ABCCCA
3 5
2 3
1 3
1 6

输出

0
1
2
2

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $S$ 只包含字符 A、B、C。
• $1 \leq Q \leq 10^5$
• $1 \leq L_i \leq R_i \leq N$
• 输入中的所有数均为整数。

样例解释 1

对于第一个询问，字符串为 $t =$ CCC，已经全部相同，答案为 $0$。
对于第二个询问，字符串为 $t =$ BC，可以选择子串 $t[2:2]$ 和排列 $(X, Y, Z) = ($A$,$C$,$B$)$，一次操作即可变为 BB。
对于第三个询问，字符串为 $t =$ ABC，可以选择子串 $t[2:3]$ 和排列 $(X, Y, Z) = ($C$,$A$,$B$)$，一次操作可变为 AAB，再选择子串 $t[1:2]$ 和排列 $(X, Y, Z) = ($B$,$A$,$C$)$，第二次操作可变为 BBB。

由 ChatGPT 4.1 翻译