题目描述

塔尖学校即将举办运动会。运动会中有一个项目，称为 魔法阵。

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

• 第 $i(1\leq i\leq n)$ 个字符 $s_i$ 为 r 则表示魔法阵 $i$ 为红色，否则为蓝色。

翁老师可以通过如下的两种方式在魔法阵中传送：

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

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

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

输入格式

第一行输入两个整数 $n,q$。

第二行输入一个字符串 $s$。

接下来 $q$ 行，每行输入两个整数 $x,y$。

输出格式

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

5 2
rbrbb
5 3
4 5

2
1

4 3
brrr
2 4
1 3
3 1

1
2
2

6 3
brbrbr
1 2
2 5
2 4

1
2
1

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

1
2
3
2
1

提示

样例 1 解释

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

对于第一组计划（$5\to 3$），翁老师可以使用如下传送方案：

• 从魔法阵 $5$ 传送到相邻的魔法阵 $1$，花费 $1$ 秒；
• 从魔法阵 $1$ 传送到颜色相同的魔法阵 $3$，花费 $1$ 秒。

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

对于第二组计划（$4\to 5$），翁老师可以使用如下传送方案：

• 从魔法阵 $4$ 传送到颜色相同的魔法阵 $5$，花费 $1$ 秒。

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

该样例满足子任务 $5,6$ 的限制。

数据范围

对于 $100\%$ 的数据满足：$3\le n\le 5\times 10^5$，$1\le q\le 5\times 10^5$，$s$ 为仅包含小写字母 b 和 r 的长度为 $n$ 的字符串，每组询问中：$1\le x,y\le n$，$x\ne y$。

• 子任务 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$ 分）无附加限制。