问题陈述

有一个大小为$H$行$W$列的网格。$(i, j)$表示从上方第$i$行，从左方第$j$列的方块。
$N$个方块，$(r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N)$，有墙壁。

高桥最初位于方块$(r_s, c_s)$。

给出$Q$个指令给高桥。对于$i = 1, 2, \ldots, Q$，第$i$个指令由一个字符$d_i$和一个正整数$l_i$表示。$d_i$是L、R、U、D中的一个，分别表示左、右、上、下的方向。

根据第$i$个方向，高桥重复以下动作$l_i$次：

如果当前方块在$d_i$表示的方向上有一个没有墙壁的方块，移动到那个方块；否则，什么也不做。

对于$i = 1, 2, \ldots, Q$，输出高桥在他按照前$i$个指令后将会到达的方块。

约束条件

• $2 \leq H, W \leq 10^9$
• $1 \leq r_s \leq H$
• $1 \leq c_s \leq W$
• $0 \leq N \leq 2 \times 10^5$
• $1 \leq r_i \leq H$
• $1 \leq c_i \leq W$
• $i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)$
• $(r_s, c_s) \neq (r_i, c_i)$对于所有$i = 1, 2, \ldots, N$。
• $1 \leq Q \leq 2 \times 10^5$
• $d_i$是字符L、R、U、D中的一个。
• $1 \leq l_i \leq 10^9$
• 输入中除了$d_i$之外的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$H$ $W$ $r_s$ $c_s$ $N$ $r_1$ $c_1$ $r_2$ $c_2$ $\vdots$ $r_N$ $c_N$ $Q$ $d_1$ $l_1$ $d_2$ $l_2$ $\vdots$ $d_Q$ $l_Q$

输出

输出$Q$行。对于$i = 1, 2, \ldots, Q$，第$i$行应该包含高桥按照前$i$个指令后将会到达的方块$(R_i, C_i)$，格式如下：

$R_1$ $C_1$ $R_2$ $C_2$ $\vdots$ $R_Q$ $C_Q$

示例输入1

5 5 4 4
3
5 3
2 2
1 4
4
L 2
U 3
L 2
R 4

示例输出1

4 2
3 2
3 1
3 5

给定的网格和高桥的初始位置如下，其中 # 表示有墙壁的方块，T 表示高桥所在的方块，. 表示其他方块：

...#.
.#...
.....
...T.
..#..

给定第$1$个指令，高桥向左移动$2$个方块，最终到达方块$(4, 2)$，如下所示：

...#.
.#...
.....
.T...
..#..

给定第$2$个指令，高桥先向上移动$1$个方块，然后因为他的方向上相邻的方块有墙壁而“什么也不做”两次。结果，他最终到达方块$(3, 2)$，如下所示：

...#.
.#...
.T...
.....
..#..

给定第$3$个指令，高桥先向左移动$1$个方块，然后因为他的方向上没有方块而“什么也不做”一次。结果，他最终到达方块$(3, 1)$，如下所示：

...#.
.#...
T....
.....
..#..

给定第$4$个指令，高桥向右移动$4$个方块，最终到达方块$(3, 5)$，如下所示：

...#.
.#...
....T
.....
..#..

示例输入2

6 6 6 3
7
3 1
4 3
2 6
3 4
5 5
1 1
3 2
10
D 3
U 3
L 2
D 2
U 3
D 3
U 3
R 3
L 3
D 1

示例输出2

6 3
5 3
5 1
6 1
4 1
6 1
4 1
4 2
4 1
5 1