题目描述

Monkeyland 是一条无限长的数轴，上面有 $n$ 只猴子，编号从 $1$ 到 $n$。第 $i$ 只猴子初始位于数轴上的位置 $p[i]$。允许多只猴子初始位于同一位置。

Pan 可以使用他的魔法让所有猴子移动！每只猴子的移动方式由一个长度为 $n$ 的字符串 $d$ 决定，其中每个字符是 L 或 R。令 $d$ 的第 $i$ 个字符为 $d[i]$。

一旦施放魔法，第 $i$ 只猴子将按如下规则移动：

• 如果 $d[i] = \text{L}$，则它向左移动 一个单位。
• 如果 $d[i] = \text{R}$，则它向右移动 一个单位。

Pan 每天会恰好施放一次魔法。如果在任意一天（包括初始时）两只猴子位于同一位置，它们就会成为 朋友。如果 Pan 连续施法 $k$ 天，请确定将会成为朋友的 猴子对 的数量。

输入格式

你的程序需要从标准输入读取数据。

输入的第一行包含两个由空格分隔的整数 $n$ 和 $k$。

输入的第二行包含 $n$ 个由空格分隔的整数 $p[1], p[2], \dots, p[n]$。

输入的第三行包含一个长度为 $n$ 的字符串 $d$，字符依次为 $d[1], d[2], \dots, d[n]$。

输出格式

你的程序需要向标准输出写入数据。

输出一个整数，表示将会成为朋友的猴子对的数量。

输出应仅包含一个整数。不要输出任何额外的文本，例如 Enter a number 或 The answer is。

2 1
1 3
RL

1

5 67
1 2 3 4 5
RRRRR

0

6 7
1 1 8 16 18 22
RRLRLL

3

10 30
9 46 27 8 12 100 56 96 6 7
LRLRRLRRLR

5

4 2
3 4 4 6
LLRL

2

提示

样例测试 #1 解释

共有 $n = 2$ 只猴子，Pan 只施法 $k = 1$ 天。

第一天，猴子 1 从位置 $1$ 向右移动到位置 $2$，而猴子 2 从位置 $3$ 向左移动到位置 $2$。由于它们在第一天结束时位于同一位置，它们成为了朋友。因此，恰好有 $1$ 对猴子成为了朋友。

样例测试 #2 解释

共有 $n = 5$ 只猴子，Pan 连续施法 $k = 67$ 天。

由于所有猴子的初始位置互不相同，且每次施法时每只猴子都向右移动一个单位，因此在任何一天都不会有两只猴子位于同一位置。所以，没有猴子对能成为朋友。

样例测试 #5 解释

共有 $n = 4$ 只猴子，Pan 连续施法 $k = 2$ 天。

下面的每张图都描绘了 Monkeyland 数轴的一部分，仅显示位置 $1$ 到 $6$。每只猴子上方的箭头表示它在施法后将移动的方向。

在第 $0$ 天，所有猴子的初始位置如下图所示。已经位于位置 $4$ 的猴子 $2$ 和猴子 $3$ 成为了朋友。

:::align{center} :::

在第 $1$ 天施法后，所有猴子的位置如下图所示。猴子 $3$ 和猴子 $4$ 在位置 $5$ 相遇并成为了朋友。

:::align{center} :::

在第 $2$ 天施法后，所有猴子的位置如下图所示。这一天没有猴子相遇。

:::align{center} :::

因此，总共有 $2$ 对猴子成为了朋友：猴子 $2$ 和 $3$，以及猴子 $3$ 和 $4$。

子任务

对于所有测试用例，输入数据满足以下限制：

• $1 \le n \le 200\,000$
• $1 \le k \le 10^9$
• 对于所有 $1 \le i \le n$，有 $1 \le p[i] \le 10^9$
• 对于所有 $1 \le i \le n$，$d[i]$ 是 L 或 R

你的程序将在满足以下限制的输入实例上进行测试：

翻译由 DeepSeek V3.2 完成