当前没有测试数据。

D - LRUD指令

分值 : $400$ 分

问题描述

有一个 $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})$。

给出 $Q$ 条指令给 Takahashi。 第 $i$ 条指令由一个字符 $d_i$ 和一个正整数 $l_i$ 表示。$d_i$ 是其中之一 L, R, U, D，分别表示左、右、上、下。

给出第 $i$ 个方向，Takahashi 重复以下动作 $l_i$ 次：

如果当前方格在 $d_i$ 方向上有一个没有墙的相邻方格，就移动到那个方格；否则，什么都不做。

对于 $i = 1, 2, \ldots, Q$，打印出 Takahashi 在执行前 $i$ 条指令后所在的方格。

约束

• $2 \leq H, W \leq 10^9$
• $1 \leq r_\mathrm{s} \leq H$
• $1 \leq c_\mathrm{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_\mathrm{s}, c_\mathrm{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_\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$ 个方格，然后 "什么都不做" 两次，因为他所在方向上的相邻方格有墙。结果，他最终到达方格 $(3, 2)$，如下所示：

``` ...#. .#... .T... ..... ..#.. ```

给定第 $3$ 条指令，Takahashi 首先向左移动 $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