AT_scpc2026_div2_d Coloring

Lulu 和 Terra 正在用红色、绿色和蓝色颜料作画。 Lulu 和 Terra 想要绘制一幅由 $N$ 个正方形格子组成、首尾相连的一行图片。首先，Terra 画好了部分图片，然后把剩下的交给 Lulu。Terra 所画的图片可以用一个长度为 $N$ 的字符串 $S$ 表示，$S$ 仅包含字符 `R`、`G`、`B` 和 `X`。如果 $S$ 的第 $i$ 个字符是 `R`，则第 $i$ 个格子被染成红色；如果是 `G`，则被染成绿色；如果是 `B`，则被染成蓝色；如果是 `X`，则该格子尚未染色。 Lulu 不喜欢 Terra 画的这幅画，因此她决定裁剪出一段区间，将这段区间变成一幅**完美的图片**。根据 Lulu 的定义，**完美的图片**需要满足以下两个条件： 1. 每个格子都必须被染成红色、绿色或蓝色中的一种。 2. Lulu 喜欢多彩的图画，因此任意两个相邻的格子的颜色必须互不相同。 Lulu 可以将尚未染色的格子染成任意颜色，也可以重新涂上 Terra 已经染色的格子。 Lulu 所选择的区间由两个整数 $l$ 和 $r$ 表示，指的是从左到右连续的第 $l$ 个到第 $r$ 个格子。对于每一种裁剪区间，请你告诉 Lulu 最少需要修改多少个格子的颜色，才能将该区间变成**完美的图片**。

输入由标准输入给出，格式如下： > $N\ Q$ > $S$ > $l_1\ r_1$ > $l_2\ r_2$ > $\vdots$ > $l_Q\ r_Q$

输出 $Q$ 行，每行包含一个整数，表示在每种情况中，Lulu 至少需要涂改多少个格子，才能将该区间变为**完美的图片**。

### 数据范围 - $1 \leq N, Q \leq 300\,000$ - 字符串 $S$ 仅由大写字母 `R`、`G`、`B` 和 `X` 组成。 - 对于每个查询，$1 \leq l_i \leq r_i \leq N$。 - 输入中的所有数字均为整数。 由 ChatGPT 5 翻译