CF1993F1.Dyn-scripted Robot (Easy Version)

这是该问题的简单版本。唯一的区别在于本版本中 $k \le n$。只有当你同时解决了两个版本的问题时，才能进行 hack。

给定一个 $w \times h$ 的矩形，位于 $Oxy$ 平面上，左下角为点 $(0, 0)$，右上角为点 $(w, h)$。

你还有一个初始位于点 $(0, 0)$ 的机器人，以及一个长度为 $n$ 的脚本 $s$。脚本 $s$ 由 $n$ 个字符组成，每个字符为 L、R、U 或 D，分别表示机器人向左、右、上、下移动。

机器人只能在矩形内部移动；如果尝试越界，则会按如下方式修改脚本 $s$：

• 如果尝试越过垂直边界，则将所有的 L 字符变为 R，所有的 R 字符变为 L。
• 如果尝试越过水平边界，则将所有的 U 字符变为 D，所有的 D 字符变为 U。

然后，机器人会从无法执行的那个字符开始，执行修改后的脚本。

这是机器人的移动过程示例，$s = \texttt{"ULULURD"}$。

脚本 $s$ 会被连续执行 $k$ 次。所有对字符串 $s$ 的修改在重复执行时都会保留。在这个过程中，机器人总共会有多少次到达点 $(0, 0)$？注意，初始位置不计入。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含四个整数 $n$、$k$、$w$ 和 $h$（$1 \le n, w, h \le 10^6$；$1 \le k \le n$）。

第二行包含一个长度为 $n$ 的字符串 $s$（$s_i \in \{\texttt{L}, \texttt{R}, \texttt{U}, \texttt{D}\}$），表示要执行的脚本。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出一个整数，表示机器人在连续执行 $k$ 次脚本 $s$ 的过程中到达 $(0, 0)$ 的总次数。

在第一个测试用例中，机器人只会向上和向右移动。最终停在 $(2, 2)$，但从未到达 $(0, 0)$，所以答案为 $0$。

在第二个测试用例中，每次执行脚本时，机器人会两次到达原点。由于 $k=2$，所以总共到达原点 $2 \cdot 2 = 4$ 次。

在第三个测试用例中，示意图如下：

由 ChatGPT 4.1 翻译