You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

刚上初一的小纯特别喜欢机器人，于是在这个周末，她报名了学校的“小机器人俱乐部”。在通过了层层考核后，她终于加入了机器人俱乐部。

现在小纯把她的机器人放入了一个 $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$ 。

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

Input Format

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

对于每组数据：

第一行三个整数$n,m,k$，表示地图边长，指令序列长度，实验次数。

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

接下来 $k$ 行，每行第一个数 $op$ 表示操作类型。

• 若 $op=1$，则下一行接下来四个整数 $x,y,l,r\ (1\leq x,y\leq n,1\leq l\leq r\leq m)$
• 若 $op=2$，则下一行接下来一个整数 $x\ (1\leq x\leq m)$ 和一个字符 $c$。

Output Format

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

Sample

样例输入

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

Hint

$1 \leq T\leq 10,1\leq n,m,k\leq 5 \times 10^5$

数据保证 $max(n,m,k)\geq 100$ 的数据不会超过两组。