Это сложная версия задачи. Единственное отличие заключается в том, что в этой версии \(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)\)? Обратите внимание, что начальная позиция не учитывается.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество раз, когда робот переместится в \((0, 0)\) при выполнении сценария \(s\) \(k\) раз подряд.
Примечание
В первом наборе входных данных робот движется только вверх и вправо при первых двух исполнениях сценария. После этого он занимает позицию \((2, 2)\). При следующих двух исполнениях он двигается вниз и влево и заканчивает в \((0, 0)\). Поэтому ответ равен \(1\).
Во втором наборе входных данных каждый раз при выполнении сценария робот посещает начало координат дважды. И поскольку \(k=2\), он посещает начало координат \(2 \cdot 2 = 4\) раза в общей сложности.
В третьем наборе входных данных визуализация показана ниже:
Примеры
| № | Входные данные | Выходные данные |
|
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
4
3
1
1
41152263332
|