AT_scpc2026_div2_d.Coloring

Lulu and Terra are playing with red, green, and blue paints.

Lulu and Terra want to paint a picture consisting of $N$ square cells arranged in a row. Terra first painted part of the picture and then handed the rest over to Lulu. The picture painted by Terra can be represented by a string $S$ of length $N$ consisting of R, G, B, and X. If the $i$-th character of $S$ is R, the $i$-th cell is painted red; if it is G, it is painted green; if it is B, it is painted blue; and if it is X, it is an unpainted empty cell.

Lulu does not like the picture Terra painted, so Lulu decided to cut out a certain interval of the picture and make that interval into a perfect picture. According to Lulu, a perfect picture is a picture satisfying the following two conditions.

1. Every cell must be painted one of red, green, and blue.

2. Lulu likes colorful things, so any two adjacent cells must always have different colors.

Lulu can paint empty cells that Terra did not paint in any desired color, and can also repaint cells Terra has already painted in a different color.

The interval Lulu cuts out is represented by two integers $l$ and $r$, meaning the consecutive interval from the $l$-th cell to the $r$-th cell from the left. For each of the $Q$ ways to cut out a certain interval, tell Lulu the minimum number of cells that must be repainted to make the interval a perfect picture.

露露和泰拉正在用红、绿、蓝三种颜料作画。

露露和泰拉想要绘制一幅由 $N$ 个正方形格子排成一行组成的画。泰拉先绘制了画的一部分，然后将剩余部分交给了露露。泰拉绘制的画可用一个长度为 $N$ 的字符串 $S$ 表示，其中字符仅包含 R、G、B 和 X。若 $S$ 的第 $i$ 个字符为 R，则第 $i$ 个格子被涂成红色；若为 G，则涂成绿色；若为 B，则涂成蓝色；若为 X，则表示该格子尚未着色（为空白格）。

露露不喜欢泰拉所绘制的画，因此决定从整幅画中裁剪出某一段连续区间，并将该区间改造成一幅完美画作。在露露看来，一幅完美画作需同时满足以下两个条件：

1. 每个格子必须被涂上红、绿、蓝三色之一；

2. 露露喜欢色彩丰富的事物，因此任意两个相邻格子的颜色必须互不相同。

露露可以将泰拉未涂色的空白格（即 X）涂成任意所需颜色，也可以将泰拉已涂色的格子重新涂成另一种颜色。

露露裁剪出的区间由两个整数 $l$ 和 $r$ 表示，意为从左起第 $l$ 个格子到第 $r$ 个格子（含端点）构成的连续区间。对于给定的 $Q$ 种裁剪区间的方式，请分别告诉露露：为使该区间成为一幅完美画作，所需重绘的格子数的最小值。

The input is given from Standard Input in the following format:

$N$ $Q$
$S$
$l_1$ $r_1$
$l_2$ $r_2$
$\vdots$
$l_Q$ $r_Q$

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

$N$ $Q$
$S$
$l_1$ $r_1$
$l_2$ $r_2$
$\vdots$
$l_Q$ $r_Q$

Print $Q$ lines. For each case, print one line containing the minimum number of cells Lulu must repaint to complete the perfect picture.

输出 $Q$ 行。对于每组测试数据，输出一行，包含 Lulu 为完成完美图片所需重绘的最少格子数。

表示言語

/ /

Constraints

• $1 \leq N, Q \leq 300\,000$
• The string $S$ consists only of uppercase letters R, G, B, and X.
• For each query, $1 \leq l_i \leq r_i \leq N$.
• All given numbers are integers.

字符串表示

/ /

约束条件

• $1 \leq N, Q \leq 300\,000$
• 字符串 $S$ 仅由大写字母 R、G、B 和 X 组成。
• 对于每个查询，满足 $1 \leq l_i \leq r_i \leq N$。
• 所有给定的数均为整数。