Codeforces Round 963 (Div. 2) |
---|
Finished |
This is the hard version of the problem. The only difference is that in this version $$$k \le 10^{12}$$$. You can make hacks only if both versions of the problem are solved.
Given a $$$w \times h$$$ rectangle on the $$$Oxy$$$ plane, with points $$$(0, 0)$$$ at the bottom-left and $$$(w, h)$$$ at the top-right of the rectangle.
You also have a robot initially at point $$$(0, 0)$$$ and a script $$$s$$$ of $$$n$$$ characters. Each character is either L, R, U, or D, which tells the robot to move left, right, up, or down respectively.
The robot can only move inside the rectangle; otherwise, it will change the script $$$s$$$ as follows:
Then, it will execute the changed script starting from the character which it couldn't execute.
The script $$$s$$$ will be executed for $$$k$$$ times continuously. All changes to the string $$$s$$$ will be retained even when it is repeated. During this process, how many times will the robot move to the point $$$(0, 0)$$$ in total? Note that the initial position does NOT count.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains four integers $$$n$$$, $$$k$$$, $$$w$$$, and $$$h$$$ ($$$1 \le n, w, h \le 10^6$$$; $$$1 \le k \le 10^{12}$$$).
The second line contains a single string $$$s$$$ of size $$$n$$$ ($$$s_i \in \{\texttt{L}, \texttt{R}, \texttt{U}, \texttt{D}\}$$$) — the script to be executed.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, print a single integer — the number of times the robot reaches $$$(0, 0)$$$ when executing script $$$s$$$ for $$$k$$$ times continuously.
62 4 2 2UR4 2 1 1LLDD6 3 3 1RLRRRL5 6 3 3RUURD7 5 3 4RRDLUUU7 123456789999 3 2ULULURD
1 4 3 1 1 41152263332
In the first test case, the robot only moves up and right for the first two executions. After that, it occupies the position $$$(2, 2)$$$. For the next two executions, it moves down and left and finishes at $$$(0, 0)$$$. So the answer is $$$1$$$.
In the second test case, each time executing the script the robot visits the origin twice. And since $$$k=2$$$, it visits the origin $$$2 \cdot 2 = 4$$$ times overall.
In the third test case, the visualization is shown as below:
Name |
---|