Dyn‑scripted Robot (Hard Version)

时间限制：3 秒
空间限制：256 MB

这是问题的困难版本，唯一的区别是 $k \le 10^{12}$。只有解决了两个版本才能进行 hack。

在平面直角坐标系中有一个 $w \times h$ 的矩形，左下角为 $(0,0)$，右上角为 $(w,h)$。

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

机器人只能在矩形内移动；否则它会按照以下规则修改脚本 $s$：

• 如果它试图移出左右边界，则将所有 L 改为 R，同时将所有 R 改为 L。
• 如果它试图移出上下边界，则将所有 U 改为 D，同时将所有 D 改为 U。

然后，它会从未能执行的那条指令开始，执行修改后的脚本。

脚本 $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 \{\text{L}, \text{R}, \text{U}, \text{D}\}$）—— 待执行的脚本。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一个整数 —— 机器人连续执行 $k$ 次脚本 $s$ 的过程中访问 $(0,0)$ 的总次数。

样例输入

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
4
3
1
1
41152263332

样例解释

• 第一个测试数据：前两次执行机器人只向上和向右移动，最终停在 $(2,2)$。后两次执行由于脚本反转，它向下和向左移动，最后回到 $(0,0)$。所以总共访问原点 $1$ 次。

• 第二个测试数据：每次执行脚本均访问原点两次，$k=2$ 时总共 $4$ 次。

• 

• 第三个测试数据：示意图见原题，答案为 $3$。

•