U534155 打磨珍珠（pearl）（T2）

$\ \ \ \ \ \ $LHRG李 喜欢的女孩过生日了，但是由于疫情影响，没办法即时送她生日礼物。于是，LHRG李决定挑选一些上好的珍珠打磨后串成项链等疫情结束后送给她。但是由于 LHRG李被她传染得比较懒，不打算自己动手打磨了，所以就制作了一个打磨珍珠的机器，利用机器进行打磨。

$\ \ \ \ \ \ $首先他把无数个珍珠排成了一长行，将机器随便放在了一个珍珠的前面，规定以这个珍珠的为原点，坐标为 $0$，其它的珍珠依次代表一个整数坐标 $i(i\in Z)$。然后，使他对机器输入了 $n$ 条命令，每条命令由一个由大写字母组成的单词 $\mathsf{LEFT}$ 或 $\mathsf{RIGHT}$ 和一个数字组成。 $\ \ \ \ \ \ $命令 $\mathsf{LEFT} \ \ 5$ 就表示使机器向左移动 $5$ 次（每一次移动到相邻的一个珍珠面前并进行打磨），命令 $\mathsf{RIGHT} \ \ 20$ 就表示使机器向右移动 $20$ 次（每一次移动到相邻的一个珍珠面前并进行打磨）。 $\ \ \ \ \ \ $由于LHRG李对送给女孩子的东西比较挑剔，所以，只有符合一下要求的珍珠才可以被串成一串： - 1、在珍珠的序列中需要是连续的 $k$ 个。 - 2、这 $k$ 个珍珠中每个珍珠的打磨次数是相同的。 - 3、这 $k$ 个珍珠的打磨次数之和 $\in(l,r)$。 $\ \ \ \ \ \ $所以给你 $n$，$k$，$l$，$r$ 和 $n$ 次命令，请你求出若只想串出一串项链，有多少种不同的选择？ $\ \ \ \ \ \ $**两种选择是相同的当且仅当其中所有的珍珠的坐标相同。**

第一行：四个整数：$n$，$k$，$l$，$r$。 第二行-第 $n+1$ 行，每行一个由大写字母构成的单词，一个整数，表示一个命令。

一个整数，表示一共有多少种不同的选择。

数据范围： | 子任务 | 测试点编号 | 总分数 | 数据范围 | | :----: | :----: | :----: | :----: | | **Subtask #1** | $1-9$ | 30 | $1\leqslant n \leqslant 100$ | | **Subtask #2** | $10-18$ | 30 | $1\leqslant n \leqslant 10000$ | | **Subtask #3** | $19-30$ | 40 | $1\leqslant n \leqslant 10^6$ | 对于 $100\%$ 的数据，$1\leqslant n \leqslant 10^6$，$1\leqslant k \leqslant 1000$，$0\leqslant l < r \leqslant 10^6$ **最远能移动到离原点 $1000000000$ 的珍珠面前。** **友情提示：输入的每一行命令之后可能有空格！** **计分规则：** $\qquad\!\!$对于每个 subtask，假设其中共有 $3k$ 个测试点，未 $AC$ 数量为 $x$。 $\qquad\!\!$$x=0$ 时，得 $10k$ 分；$x\leqslant k$ 时，得 $10k-4x$ 分；$x>k$ 时，得 $6k-3(x-k)$ 分。 $\qquad\!\!$[计分脚本](http://lhrg.github.io/打磨珍珠subtask计分脚本/) [题解](http://lhrg.github.io/题解-U534155-【打磨珍珠】/) ------------------------- 出题者：LHRG李