在比太郎就读的魔法学校里，马上就要举办运动会了。运动会的其中一个比赛项目是尽快从起点的魔法阵移动到终点的魔法阵。

比赛中，有 $N$ 个魔法阵等间距地围成一个圆圈，顺时针编号 $1$ 到 $N$。每个魔法阵要么是蓝色，要么是红色。颜色信息由长度为 $N$ 的仅包含 b 和 r 的字符串 $S$ 给出，第 $j$ 个字符（$1 \leq j \leq N$）为 b 时表示第 $j$ 个魔法阵是蓝色，为 r 时表示红色。

比太郎在比赛中可以使用以下两种移动方式：

• 选择相邻的魔法阵之一，花费 $1$ 秒移动到该魔法阵。即，可以从魔法阵 $j$ 移动到 $j+1$（$1 \leq j \leq N-1$），或者从 $1$ 号魔法阵移动到 $N$ 号魔法阵，花费 $1$ 秒。
• 选择任意一个与当前魔法阵颜色相同的魔法阵，花费 $1$ 秒移动到该魔法阵。

现在已知各个魔法阵的数量和颜色信息，但只有到比赛当天才能知道具体的起点和终点。为了做好准备，比太郎考虑了 $Q$ 种起点和终点的组合，对于每种情况，他想提前求出从起点到终点所需的最小时间。

对于第 $i$ 种情况（$1 \leq i \leq Q$），起点为第 $X_i$ 号魔法阵，终点为第 $Y_i$ 号魔法阵。

给定所有魔法阵的信息及多种起点和终点的组合，请编程求出每种情况下比太郎从起点移动到终点所需的最小时间。

---

输入由以下格式组成，从标准输入读入：

$N$ $Q$ $S$ $X_1$ $Y_1$ ⋮ $X_Q$ $Y_Q$

请输出 $Q$ 行，第 $i$ 行（$1 \leq i \leq Q$）输出比太郎从魔法阵 $X_i$ 移动到 $Y_i$ 的最小所需时间（单位：秒）。

小题目

1. ($6$ 分) $N=3$，且 $Q \leq 100$。
2. ($13$ 分) $S$ 的第 $1$ 个字符为 b，第 $2$ 个及之后的字符均为 r。
3. ($18$ 分) $N$ 是偶数，$S$ 的奇数位置是 b，偶数位置是 r。
4. ($23$ 分) $N$ 是偶数，$S$ 的前一半为 b，后一半为 r。
5. ($21$ 分) $N \leq 100$，$Q \leq 100$。
6. ($19$ 分) 无其他限制。

---

样例说明 1

在本例中，依次为红、蓝、红、蓝、蓝色的魔法阵按圆形顺序排列。

对于第 $1$ 组起终点，比太郎可以如下移动，从魔法阵 $5$ 到 $3$ 只需 $2$ 秒：

1. 魔法阵 $5$ 和魔法阵 $1$ 相邻，所以从 $5$ 号移动到 $1$ 号魔法阵用 $1$ 秒。
2. 魔法阵 $1$ 和魔法阵 $3$ 都是红色，可以直接从 $1$ 号移动到 $3$ 号魔法阵用 $1$ 秒。

无法在 $2$ 秒之内完成，因此第 $1$ 行输出 $2$。

对于第 $2$ 组起终点，比太郎可以如下移动，从魔法阵 $4$ 到 $5$ 只需 $1$ 秒：

1. 魔法阵 $4$ 和魔法阵 $5$ 都是蓝色，可以直接从 $4$ 号移动到 $5$ 号魔法阵用 $1$ 秒。

无法在 $1$ 秒之内完成，因此第 $2$ 行输出 $1$。

此输入样例满足小题目 $5, 6$ 的限制条件。

---

样例说明 2

此输入样例满足小题目 $2, 5, 6$ 的限制条件。

---

样例说明 3

此输入样例满足小题目 $3, 5, 6$ 的限制条件。

---

样例说明 4

此输入样例满足小题目 $4, 5, 6$ 的限制条件。

数据范围与限制

• $3 \leq N \leq 500,\!000$。
• $1 \leq Q \leq 500,\!000$。
• $S$ 是由 b 和 r 组成的长度为 $N$ 的字符串。
• $1 \leq X_i \leq N$（$1 \leq i \leq Q$）。
• $1 \leq Y_i \leq N$（$1 \leq i \leq Q$）。
• $X_i \neq Y_i$（$1 \leq i \leq Q$）。
• $N, Q, X_i, Y_i$ 均为整数（$1 \leq i \leq Q$）。

由 ChatGPT 5 翻译