LRUD 指令

题目描述

有一个 $H$ 行 $W$ 列的网格。$(i, j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。

有 $N$ 个格子 $(r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N)$ 上放有墙壁。

Takahashi 最初在格子 $(r_\mathrm{s}, c_\mathrm{s})$ 上。

给 Takahashi $Q$ 条指令。 对于 $i = 1, 2, \ldots, Q$,第 $i$ 条指令由字符 $d_i$ 和正整数 $l_i$ 组成。$d_i$ 是 L、R、U、D 之一,分别表示左、右、上、下四个方向。

给定第 $i$ 个方向后,Takahashi 将下面的动作重复执行 $l_i$ 次:

如果当前格子沿 $d_i$ 方向相邻的格子没有墙,就移动到那个格子; 否则,什么也不做。

对于 $i = 1, 2, \ldots, Q$,输出 Takahashi 执行完前 $i$ 条指令后所在的格子。

输入格式

输入按以下格式从标准输入给出:

$H$ $W$ $r_\mathrm{s}$ $c_\mathrm{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$ 行按以下格式输出 Takahashi 执行完前 $i$ 条指令后所在的格子 $(R_i, C_i)$:

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

样例

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

4 2
3 2
3 1
3 5

给定的网格和 Takahashi 的初始位置如下,其中 # 表示有墙的格子,T 表示 Takahashi 所在的格子,. 表示其余格子:

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

执行第 $1$ 条指令后,Takahashi 向左移动 $2$ 格,到达格子 $(4, 2)$,如下所示:

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

执行第 $2$ 条指令后,Takahashi 先向上移动 $1$ 格,然后因为该方向相邻的格子有墙,「什么也不做」执行了 $2$ 次。结果他到达格子 $(3, 2)$,如下所示:

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

执行第 $3$ 条指令后,Takahashi 先向左移动 $1$ 格,然后因为该方向已经没有格子,「什么也不做」执行了 $1$ 次。结果他到达格子 $(3, 1)$,如下所示:

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

执行第 $4$ 条指令后,Takahashi 向右移动 $4$ 格,到达格子 $(3, 5)$,如下所示:

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

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

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

数据范围

• $2 \le H, W \le 10^9$
• $1 \le r_\mathrm{s} \le H$
• $1 \le c_\mathrm{s} \le W$
• $0 \le N \le 2 \times 10^5$
• $1 \le r_i \le H$
• $1 \le c_i \le W$
• $i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)$
• 对于所有 $i = 1, 2, \ldots, N$,有 $(r_\mathrm{s}, c_\mathrm{s}) \neq (r_i, c_i)$
• $1 \le Q \le 2 \times 10^5$
• $d_i$ 是 L、R、U、D 之一
• $1 \le l_i \le 10^9$
• 除 $d_i$ 外,输入中的所有值均为整数。