P13735 [JOIGST 2025] 魔法阵 / Magic Circle

比太郎所在的魔法学校即将举办运动会。运动会中有一个项目，称为“魔法阵”。 有 $N$ 个魔法阵依次排列在一个圆上，顺时针编号为 $1$ 到 $N$。每个魔法阵为红色或蓝色中的一种，使用长度为 $N$ 且仅包含小写字母 `b` 和 `r` 字符串 $S$ 表示：$S_j(1\le j\le N)$ 为 `r` 则表示魔法阵 $j$ 为红色，否则为蓝色。 比太郎可以通过如下的两种方式在魔法阵中传送： - 选择一个相邻的魔法阵，花费 $1$ 秒传送过去。换句话说，可以在魔法阵 $j(1\le j\le N-1)$ 和 $j+1$ 间传送（两个方向均可），也可以在魔法阵 $1$ 和 $N$ 间传送（两个方向均可）； - 选择一个与当前所在魔法阵颜色相同的魔法阵（不一定要相邻），花费 $1$ 秒传送过去。 目前他仅得知每个魔法阵的颜色，但并不知道运动会当天具体的传送计划。于是他决定考虑 $Q$ 个传送计划：在第 $i$ 个计划中，他要从魔法阵 $X_i$ 开始，花费最少的时间传送到魔法阵 $Y_i$。 请你对于每一个传送计划，求出最少需要花费的时间。

第一行输入两个整数 $N,Q$。 第二行输入一个字符串 $S$。 接下来 $Q$ 行，每行输入两个整数 $X_i,Y_i$。

输出 $Q$ 行，在第 $i$ 行输出一个整数，表示第 $i$ 个传送计划最少需要花费的传送时间（单位：秒）。

#### 【样例解释 #1】 在此样例中，魔法阵的颜色分别为红色、蓝色、红色、蓝色、蓝色。 对于第一组计划（$5\to 3$），比太郎可以使用如下传送方案： 1. 从魔法阵 $5$ 传送到相邻的魔法阵 $1$，花费 $1$ 秒； 2. 从魔法阵 $1$ 传送到颜色相同的魔法阵 $3$，花费 $1$ 秒。 最少需要花费的时间为 $2$ 秒。可以证明不可能在小于 $2$ 秒的时间内从魔法阵 $5$ 传送到魔法阵 $3$。 对于第二组计划（$4\to 5$），比太郎可以使用如下传送方案： 1. 从魔法阵 $4$ 传送到颜色相同的魔法阵 $5$，花费 $1$ 秒。 最少需要花费的时间为 $1$ 秒。 该样例满足子任务 $5,6$ 的限制。 #### 【样例解释 #2】 该样例满足子任务 $2,5,6$ 的限制。 #### 【样例解释 #3】 该样例满足子任务 $3,5,6$ 的限制。 #### 【样例解释 #4】 该样例满足子任务 $4,5,6$ 的限制。 #### 【数据范围】 - $3\le N\le 5\times 10^5$； - $1\le Q\le 5\times 10^5$； - $S$ 为仅包含小写字母 `b` 和 `r` 的长度为 $N$ 的字符串； - $1\le X_i,Y_i\le N(1\le i\le Q)$； - $X_i\ne Y_i(1\le i\le Q)$。 #### 【子任务】 1. （$6$ 分）$N=3$，$Q\le 100$； 2. （$13$ 分）$S_1$ 为 `b`，$S$ 的其他字符均为 `r`； 3. （$18$ 分）$N$ 为偶数，$S$ 奇数位置的字符为 `b`，偶数位置的字符为 `r`； 4. （$23$ 分）$N$ 为偶数，$S$ 的前 $\frac{N}{2}$ 个字符为 `b`，后 $\frac{N}{2}$ 个字符为 `r`； 5. （$21$ 分）$N,Q\le 100$； 6. （$19$ 分）无附加限制。