#213824. [JOIGST 2025] 魔法阵 / Magic Circle

比太郎所在的魔法学校即将举办运动会。运动会中有一个项目，称为“魔法阵”。

有 个魔法阵依次排列在一个圆上，顺时针编号为 到 。每个魔法阵为红色或蓝色中的一种，使用长度为 且仅包含小写字母 b 和 r 字符串 表示： 为 r 则表示魔法阵 为红色，否则为蓝色。

比太郎可以通过如下的两种方式在魔法阵中传送：

• 选择一个相邻的魔法阵，花费 秒传送过去。换句话说，可以在魔法阵 和 间传送（两个方向均可），也可以在魔法阵 和 间传送（两个方向均可）；
• 选择一个与当前所在魔法阵颜色相同的魔法阵（不一定要相邻），花费 秒传送过去。

目前他仅得知每个魔法阵的颜色，但并不知道运动会当天具体的传送计划。于是他决定考虑 个传送计划：在第 个计划中，他要从魔法阵 开始，花费最少的时间传送到魔法阵 。

请你对于每一个传送计划，求出最少需要花费的时间。

第一行输入两个整数 。

第二行输入一个字符串 。

接下来 行，每行输入两个整数 。

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

样例输入 1

5 2
rbrbb
5 3
4 5

样例输出 1

2
1

样例输入 2

4 3
brrr
2 4
1 3
3 1

样例输出 2

1
2
2

样例输入 3

6 3
brbrbr
1 2
2 5
2 4

样例输出 3

1
2
1

样例输入 4

6 5
bbbrrr
2 3
2 4
2 5
2 6
2 1

样例输出 4

1
2
3
2
1

【样例解释 #1】

在此样例中，魔法阵的颜色分别为红色、蓝色、红色、蓝色、蓝色。

对于第一组计划（），比太郎可以使用如下传送方案：

1. 从魔法阵 传送到相邻的魔法阵 ，花费 秒；
2. 从魔法阵 传送到颜色相同的魔法阵 ，花费 秒。

最少需要花费的时间为 秒。可以证明不可能在小于 秒的时间内从魔法阵 传送到魔法阵 。

对于第二组计划（），比太郎可以使用如下传送方案：

1. 从魔法阵 传送到颜色相同的魔法阵 ，花费 秒。

最少需要花费的时间为 秒。

该样例满足子任务 的限制。

【样例解释 #2】

该样例满足子任务 的限制。

【样例解释 #3】

该样例满足子任务 的限制。

【样例解释 #4】

该样例满足子任务 的限制。

【数据范围】

• ；
• ；
• 为仅包含小写字母 b 和 r 的长度为 的字符串；
• ；
• 。

【子任务】

1. （ 分），；
2. （ 分） 为 b， 的其他字符均为 r；
3. （ 分） 为偶数， 奇数位置的字符为 b，偶数位置的字符为 r；
4. （ 分） 为偶数， 的前 个字符为 b，后 个字符为 r；
5. （ 分）；
6. （ 分）无附加限制。