这是问题的困难版本。唯一的区别是在这个版本中 $$$k \le 10^{12}$$$。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
给定 $$$Oxy$$$ 平面上的 $$$w \times h$$$ 矩形,点 $$$(0, 0)$$$ 位于矩形的左下角,$$$(w, h)$$$ 位于矩形的右上角。
您还有一个最初位于 $$$(0, 0)$$$ 点的机器人和一个包含 $$$n$$$ 个字符的脚本 $$$s$$$。每个字符都是 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 10^{12}$$$)。
第二行包含一个大小为 $$$n$$$ 的字符串 $$$s$$$ ($$$s_i \in \{\texttt{L}, \texttt{R}, \texttt{U}, \texttt{D}\}$$$) — 要执行的脚本。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,打印一个整数 - 当连续执行 $$$s$$$ 脚本 $$$k$$$ 次时,机器人到达 $$$(0, 0)$$$ 的次数。
示例
输入 #1
6 2 4 2 2 UR 4 2 1 1 LLDD 6 3 3 1 RLRRRL 5 6 3 3 RUURD 7 5 3 4 RRDLUUU 7 123456789999 3 2 ULULURD
输出 #1
1 4 3 1 1 41152263332
注意
在第一个测试用例中,机器人仅在前两次执行中向上和向右移动。之后,它占据位置$$$(2, 2)$$$。对于接下来的两次执行,它向下和向左移动并在 $$$(0, 0)$$$ 处结束。所以答案是$$$1$$$。
在第二个测试用例中,每次执行脚本时,机器人都会访问原点两次。由于 $$$k=2$$$,它总共访问原点 $$$2 \cdot 2 = 4$$$ 次。
在第三个测试用例中,可视化如下所示: