配点: 100 点
。比太郎就读的魔法学校,不久将举办运动会。运动会中,会有从起点魔法阵到终点魔法阵快速移动的竞技。
在这个竞技中,N 个魔法阵等间距排列成圆形,并且按时针方向编号到 1 到 N 。每个魔法阵都是蓝色或红色。
这些颜色信息由 b, r 构成的长度为 N 字符串
给出了 S 提供,S 的 j 文字目 (1 \leqq j \leqq N) 如果 b ,魔法阵 j 将是蓝色。r ,魔法阵 j 是红色的。
比太郎在这次竞技中可以使用以下 2 种类的移动手段。
- 选择一个与当前魔法阵相邻的魔法阵,花费 1 秒移动到该魔法阵。 也就是说,魔法阵 j 和魔法阵 j + 1 (1 \leqq j \leqq N - 1) 的之间,魔法阵 1 和魔法阵 N 的之间 1 花费秒数移动.
- 选择与当前魔法阵相同颜色的一个魔法阵,移向那个魔法阵 1 花费秒数移动.
现在,虽然知道魔法阵的数量和颜色信息,但哪个魔法阵是起点和终点,要到运动会当天才能知道。 于是,考虑起点和终点魔法阵的组合 Q 模式,事先求出每种情况需要多少秒。 模式 i (1 \leqq i \leqq Q) 中,起点是魔法阵 X_i,目标是魔法阵 Y_i 。
当给定魔法阵的信息和模式的信息时,请编写程序求出每个模式下比太郎从起点移动到目标所需时间的最小值。
入力
输入是按以下格式从标准输入给出的。
N Q S X_1 Y_1 \vdots X_Q Y_Q
出力
标准输出为 Q 行。 i 行目 (1 \leqq i \leqq Q) 比太郎移动到魔法阵 X_i 到 Y_i 所需时间的最小值(秒)。
制約
- 3 \leqq N \leqq 500\,000.
- 1 \leqq Q \leqq 500\,000.
- S 满足
b,r构成的长度为 N 字符串。 - 1 \leqq X_i \leqq N (1 \leqq i \leqq Q).
- 1 \leqq Y_i \leqq N (1 \leqq i \leqq Q).
- X_i \neq Y_i (1 \leqq i \leqq Q).
- N, Q, X_i, Y_i 是一个整数 (1 \leqq i \leqq Q).
小課題
- (6 点) N = 3,Q \leqq 100.
- (13 点) S 满足 1 仅限字符
b和2 第一个字符之后的所有内容r。 - (18 点) N 是偶数,S 是奇数字符。
b,偶数字符r。 - (23 点) N 是偶数,S 是上半场 \frac{N}2 字符是
b,下半场 \frac{N}2 字符是r。 - (21 点) N \leqq 100,Q \leqq 100.
- (19 点)没有额外的限制。
入力例 1
5 2 rbrbb 5 3 4 5
出力例 1
2 1
在这个例子中,红、蓝、红、蓝、蓝的魔法阵按照这个顺序排列成一个圆圈。
模式 关于 1 ,Bitaro如下创建了一个魔法阵。 来自 5 的魔法阵 至 3 可以在 2 秒内移动:
- 魔法陣 5 和魔法阵 1 相邻,所以魔法阵 在 5 的魔法阵 至 1 可以在 1 秒内移动。
- 魔法陣 1 和魔法阵 3 都是红色的,所以魔法阵 由于不可能在 1 的魔法阵 至 3 可以在 1 秒内移动。
2 秒内移动, 在1 行中, 2 。
模式 关于 2 ,Bitaro如下创建了一个魔法阵。 来自 4 的魔法阵 至 5 可以在 1 秒内移动:
- 魔法陣 4 和魔法阵 5 都是蓝色的,所以魔法阵 4 的魔法阵 至 5 可以在 1 秒内移动。
1 秒内移动, 在2 行中, 1 。
因此,这个输入例是小课题。 5, 6 满足约束。
入力例 2
4 3 brrr 2 4 1 3 3 1
出力例 2
1 2 2
因此,这个输入例是小课题。 2, 5, 6 满足约束。
入力例 3
6 3 brbrbr 1 2 2 5 2 4
出力例 3
1 2 1
因此,这个输入例是小课题。 3,5,6 满足约束。
入力例 4
6 5 bbbrrr 2 3 2 4 2 5 2 6 2 1
出力例 4
1 2 3 2 1
因此,这个输入例是小课题。 4,5,6 满足约束。