codeforces#P1993F1. Dyn-scripted Robot (Easy Version)
Dyn-scripted Robot (Easy Version)
Description
This is the easy version of the problem. The only difference is that in this version $k \le n$. 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:
- If it tries to move outside a vertical border, it changes all L characters to R's (and vice versa, all R's to L's).
- If it tries to move outside a horizontal border, it changes all U characters to D's (and vice versa, all D's to U's).
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 n$).
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.
Input
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 n$).
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$.
Output
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.
5
2 2 2 2
UR
4 2 1 1
LLDD
6 3 3 1
RLRRRL
5 5 3 3
RUURD
7 5 3 4
RRDLUUU
0
4
3
0
1
Note
In the first test case, the robot only moves up and right. In the end, it occupies the position $(2, 2)$ but never visits $(0, 0)$. So the answer is $0$.
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: