题目描述

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

有 $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$ 个传送计划最少需要花费的传送时间（单位：秒）。

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$），比太郎可以使用如下传送方案：

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