题目描述

注意：此题的时间限制是 4 秒，内存限制是 512MB，是默认值的两倍。

农民约翰有 $N$ ($2 \le N \le 2 \cdot 10^5$) 台拖拉机，其中第 $i$ 台拖拉机只能在序列 $[l_i,r_i]$ 内使用。拖拉机满足左端点 $l_1<l_2<\cdots <l_N$ 和右端点 $r_1<r_2< \cdots <r_N$。有一些拖拉机是特别的。

如果 $[l_i,r_i]$ 和 $[l_j,r_j]$ 相交，则称两台拖拉机 $i$ 和 $j$ 是相邻的。约翰可以从一辆拖拉机转移到任何相邻的拖拉机上。两台拖拉机 $a$ 和 $b$ 之间的路径由一个传输序列组成，序列中的第一个拖拉机是 $a$，最后一个拖拉机是 $b$，并且序列中的每两个连续的拖拉机相邻。保证拖拉机 $1$ 和拖拉机 $N$ 之间有一条路径。路径的长度是转移的次数（或等价地，其中拖拉机的数量减去 $1$）。

给定 $Q$ ($1 \le Q \le 2 \cdot 10^5$) 组询问，每次给定 $a$ 和 $b$ ($1 \le a<b \le N$)。对于每组询问，你需要回答两个问题：

• $a$ 到 $b$ 的最短路径长度。
• 在保证传送次数的最少的情况下，有多少个特殊拖拉机的区间可能被某条最短路经过。

输入格式

第一行输入两个整数 $N$ 和 $Q$，表示有 $N$ 台拖拉机和 $Q$ 次询问。

第二行输入一个长度为 $2N$ 的字符串，由大写字母 L 和 R 组成，其中第 $i$ 个 L 或 R 的位置表示 $l_i$ 或 $r_i$，保证这个字符串的每个前缀中 L 的数量大于 R 的数量。

第三行输入一个长度为 $N$ 的字符串，表示每个拖拉机是否特殊。

接下来 $Q$ 行输入两个整数 $a$ 和 $b$，表示一次查询。

输出格式

对于每一组数据，一行两个数，表示答案。

8 10
LLLLRLLLLRRRRRRR
11011010
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5

1 2
1 1
1 2
2 4
2 3
2 4
2 3
1 1
1 2
1 2

提示

样例 $1$ 解释

$8$ 个拖拉机的区间按顺序分别是 $[1,5],[2,10],[3,11],[4,12],[6,13],[7,14],[8,15],[9,16]$。

对于第四个查询，第 $1$ 台和第 $5$ 台拖拉机之间有三条最短路径: $1 \rightarrow 2 \rightarrow 5$，$1 \rightarrow 3 \rightarrow 5$ 和 $1 \rightarrow 4 \rightarrow 5$。这些最短路径的长度都为 $2$。

另外，拖拉机 $1,2,3,4,5$ 都是前面提到的三条最短路径之一的一部分，由于 $1,2,4,5$ 是特殊的，因此有 $4$ 台特殊拖拉机，这样存在至少一条包含拖拉机 $1$ 到 $5$ 的最短路径。

特殊性质：

• 数据点 $2,3$：$N,Q \le 5000$。
• 数据点 $4\sim7$：最多存在 $10$ 台特殊的拖拉机。
• 数据点 $8\sim16$：没有额外的约束。

Translated by shuqiang，fixed by tallnut