Codeforces Round 963 (Div. 2) |
---|
Finished |
This is the easy version of the problem. The only difference is that in this version k≤n. You can make hacks only if both versions of the problem are solved.
Given a w×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≤t≤104) — the number of test cases.
The first line of each test case contains four integers n, k, w, and h (1≤n,w,h≤106; 1≤k≤n).
The second line contains a single string s of size n (si∈{L,R,U,D}) — the script to be executed.
It is guaranteed that the sum of n over all test cases does not exceed 106.
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.
52 2 2 2UR4 2 1 1LLDD6 3 3 1RLRRRL5 5 3 3RUURD7 5 3 4RRDLUUU
0 4 3 0 1
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⋅2=4 times overall.
In the third test case, the visualization is shown as below:
Name |
---|