Robot
Description
Xiaochun, who has just started middle school, has a special fondness for robots. This weekend, she registered for the school's 'Little Robot Club'. After passing several rounds of exams, she finally managed to join the robot club.
Now, Xiaochun has placed her robot on an $n\times n$ grid, where both rows and columns are numbered from $1$ to $n$. She has pre-programmed a sequence of instructions with a length of $m$ in her remote control. These instructions include U,D,L,R:
- U: Move from $(x,y)$ to $(x-1,y)$.
- D: Move from $(x,y)$ to $(x+1,y)$.
- L: Move from $(x,y)$ to $(x,y-1)$.
- R: Move from $(x,y)$ to $(x,y+1)$.
Specifically, if the robot attempts to move outside the grid, that instruction is invalid.
Xiaochun has conducted a series of experiments, which fall into two categories:
- Running experiments: She provides a coordinate $(x,y)$ to place the robot and specifies a range $[l, r]$, indicating that the instructions numbered from $l$ to $r$ should be executed in sequence.
- Modification experiments: She gives a position $x$ and an instruction $c$, which means replacing the instruction at the $x$-th position in the sequence with $c$.
For each of these experimental runs, Xiaochun wants to know where her robot will ultimately stop, allowing her to verify if her robot's operation is normal.
The first line contains a positive integer $T\ (1\le T \le 10)$, representing the number of sets of data.
For each set of data:
The first line consists of three integers, $n$, $m$, and $k$, indicating the map's side length, the length of the instruction sequence, and the number of experiments, respectively. $(1 \le n, m, k \le 5 \times 10^5)$
The second line contains a string of length m, representing the instruction sequence, consisting only of the characters UDLR.
Following are $k$ lines, each beginning with the integer $op$, which represents the type of experiment:
- If $op = 1$, then the line is followed by four integers $x, y, l, r\ (1 \le x,y \le n, 1 \le l \le r \le m)$
- If $op = 2$, then the line is followed by an integer $x\ (1 \le x \le m)$ and a character $c$.
For datasets where $max(n,m,k)\ge 100$, there will be no more than two such datasets.
For each instruction where $op=1$, output two numbers $x$ and $y$ to represent the final position of the robot.
Input
The first line contains a positive integer $T\ (1\le T \le 10)$, representing the number of sets of data.
For each set of data:
The first line consists of three integers, $n$, $m$, and $k$, indicating the map's side length, the length of the instruction sequence, and the number of experiments, respectively. $(1 \le n, m, k \le 5 \times 10^5)$
The second line contains a string of length m, representing the instruction sequence, consisting only of the characters UDLR.
Following are $k$ lines, each beginning with the integer $op$, which represents the type of experiment:
- If $op = 1$, then the line is followed by four integers $x, y, l, r\ (1 \le x,y \le n, 1 \le l \le r \le m)$
- If $op = 2$, then the line is followed by an integer $x\ (1 \le x \le m)$ and a character $c$.
For datasets where $max(n,m,k)\ge 100$, there will be no more than two such datasets.
Output
For each instruction where $op=1$, output two numbers $x$ and $y$ to represent the final position of the robot.
1
5 5 4
RDRRD
1
5 3 1 5
1
5 1 4 5
2
1 L
1
2 3 1 5
5 5
5 2
4 4