F2. Динамически управляемый робот (Сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие заключается в том, что в этой версии $$$k \le 10^{12}$$$. Вы можете делать взломы только в том случае, если обе версии задачи решены.

Дан прямоугольник размером $$$w \times h$$$ на плоскости $$$Oxy$$$, с точками $$$(0, 0)$$$ в нижнем левом углу и $$$(w, h)$$$ в верхнем правом углу прямоугольника.

У вас также есть робот, изначально находящийся в точке $$$(0, 0)$$$, и сценарий $$$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 10^{12}$$$).

Вторая строка содержит строку $$$s$$$ размера $$$n$$$ ($$$s_i \in \{\texttt{L}, \texttt{R}, \texttt{U}, \texttt{D}\}$$$) — сценарий, который необходимо выполнить.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество раз, когда робот переместится в $$$(0, 0)$$$ при выполнении сценария $$$s$$$ $$$k$$$ раз подряд.

Пример
Входные данные
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$$$, он посещает начало координат $$$2 \cdot 2 = 4$$$ раза в общей сложности.

В третьем наборе входных данных визуализация показана ниже: