Farmer John 有 $N$ ($2\le N\le 2\cdot 10^5$) 台拖拉机，其中第 $i$ 台拖拉机只能在闭区间 $[\ell_i,r_i]$ 内使用。这些拖拉机区间的左端点满足 $\ell_1 < \ell_2 < \dots < \ell_N$，右端点满足 $r_1 < r_2 < \dots < r_N$。其中一些拖拉机是特殊的。

如果两个拖拉机 $i$ 和 $j$ 的区间 $[\ell_i,r_i]$ 和 $[\ell_j,r_j]$ 相交，则称它们是相邻的。Farmer John 可以从一台拖拉机转移到任何相邻的拖拉机。两个拖拉机 $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$ 的任意最短路径的长度。
• 满足“存在至少一条从拖拉机 $a$ 到拖拉机 $b$ 的最短路径包含该拖拉机”条件的特殊拖拉机的数量。

输入格式

第一行包含 $N$ 和 $Q$。

下一行包含一个长度为 $2N$ 的字符串，由 'L' 和 'R' 组成，表示按顺序排列的左端点和右端点。保证对于该字符串的每个真前缀，'L' 的数量都超过 'R' 的数量。

下一行包含一个长度为 $N$ 的位串，表示每台拖拉机是否为特殊拖拉机。

接下来的 $Q$ 行，每行包含两个整数 $a$ 和 $b$，表示一次查询。

输出格式

对于每次查询，输出两个由空格分隔的数值。

样例

样例输入 1

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

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$ 台拖拉机之间有三条最短路径：$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：无附加限制。