机器人

刚上初一的小纯特别喜欢机器人，这周末，她报名了学校的"小机器人俱乐部"。通过层层考试，他终于通加入了机器人俱乐部。


现在小纯把他的机器人放入了一个 $n\times n$ 的地图里，行和列都从 $1$ 到 $n$ 编号。同时小纯在他的遥控器里预设了一条长度为 $m$ 的指令，指令包括有 `U,D,L,R`：

- `U`：从 $(x,y)$ 走到 $(x-1,y)$；
- `D`：从 $(x,y)$ 走到 $(x+1,y)$；
- `L`：从 $(x,y)$ 走到 $(x,y-1)$；
- `R`：从 $(x,y)$ 走到 $(x,y+1)$。

特别地，如果机器人试图走出地图，该指令无效。

现在小纯进行了 $k$ 次实验，实验包括两种：

1. 运行实验。他会给出一个坐标 $(x,y)$，表示把机器人放了 $(x,y)$ 这个地方，然后给出一个区间 $[l,r]$，表示依次执行编号从 $l$ 到 $r$ 的指令。
2. 更改实验。他会给出一个位置 $x$，以及一个指令 $c$。代表把指令序列的第 $x$ 个位置更改为 $c$。

对于每一次运行实验，小纯想知道他的机器人最终会停在哪里，以便他测试他的机器人是否运作是正常的。

第一行一个正整数 $T$，表示数据组数。

对于每组数据：

第一行三个整数 $n,m,k$，表示地图边长、指令序列长度、实验次数。（$1 \le n,m,k \le 5 \times 10^5$）

第二行一个长度为 $m$ 的字符串，表示指令序列，仅由 `UDLR` 组成。

接下来 $k$ 行，每行第一个数 $op$ 表示实验类型，

- 若 $op=1$，则接下来一行来四个整数 $x,y,l,r$；（$1\le x,y \le n,\ 1 \le l \le r \le m$）
- 若 $op=2$，则接下来一行一个整数 $x$ 和一个字符 $c$。（$1 \le x \le m$）

$T \le 10$，且 $\max(n,m,k) \ge 100$的数据不超过两组。

对于每一个 $op=1$ 的指令，输出两个数 $x,y$ 表示最终机器人停的位置。

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

2022 CCPC 华为云计算挑战赛