题目描述

题目译自 USACO 2023 January Contest, Platinum Problem 1. Tractor Paths

FJ 有 $N$ 台拖拉机，第 $i$ 台拖拉机只能在闭区间 $[l_i,r_i]$ 中使用。拖拉机区间的端点满足 $l_1<l_2<\ldots<l_N$ 且 $r_1<r_2<\ldots<r_N$。一些拖拉机是特别的。

如果 $[l_i,r_i]$ 和 $[l_j,r_j]$ 相交，则称两台拖拉机 $i$ 和 $j$ 为相邻的。FJ 可以从一台拖拉机转移到任意相邻的拖拉机上。两拖拉机 $a$ 和 $b$ 之间的路径是由一个转移序列组成的，这个序列中第一台拖拉机是 $a$，最后一台拖拉机是 $b$，且序列中每两台连续的拖拉机都是相邻的。保证存在一条从拖拉机 $1$ 到拖拉机 $N$ 的路径。路径的长度是转移的次数（或者等价地，是序列中拖拉机个数减 $1$）。

给你 $Q$ 个询问，每个询问指定了一对拖拉机 $a$ 和 $b$。对于每个询问，输出两个整数：

• 拖拉机 $a$ 和 $b$ 之间任意最短路径的长度。
• 有多少特别的拖拉机，满足至少有一条从拖拉机 $a$ 到拖拉机 $b$ 的最短路径包含它。

输入格式

第一行两个整数 $N\ (2\le N\le 2\cdot 10^5)$ 和 $Q\ (1\le Q\le 2\cdot 10^5)$。

接下来一行一个长度为 $2N$ 的字符串，字符串中只包含 L 和 R 两种字符，表示排好序后的左右端点。保证对于这个字符串的所有正规前缀（不包括空串和全串），L 的个数多于 R 的个数。

接下来一行一个长为 $N$ 的二进制串，表示每台拖拉机是否是特别的。

接下来 $Q$ 行每行两个整数 $a$ 和 $b\ (1\le a<b\le N)$，表示一组询问。

输出格式

对于每个询问，输出一行两个整数，整数之间用一个空格隔开。

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

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

对于第 $4$ 个询问，第 $1$ 台拖拉机和第 $5$ 台拖拉机之间有 $3$ 条最短路径：$1\to 2\to 5,1\to 3\to 5,1\to 4\to 5$。这些最短路径长度都是 $2$。

此外，拖拉机 $1,2,3,4,5$ 都是前面提到的三条最短路径中的一部分，由于拖拉机 $1,2,4,5$ 是特别的，所以有 $4$ 台特别的拖拉机，满足至少有一条从拖拉机 $1$ 到 $5$ 的最短路径包含它。

数据范围与提示

• 2-3 组数据：$N,Q\le 5000$
• 4-7 组数据：最多有 $10$ 个特别的拖拉机
• 8-16 组数据：无附加限制