AT_abc273_d [ABC273D] LRUD Instructions

有一个 $H$ 行 $W$ 列的网格。自上而下的第 $i$ 行，自左而右的第 $j$ 列的格子记作格子 $(i,\,j)$。 有 $N$ 个格子 $(r_1,\,c_1),\ (r_2,\,c_2),\ \ldots,\ (r_N,\,c_N)$ 是墙。 一开始，高桥君位于格子 $(r_\mathrm{s},\,c_\mathrm{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$ 条指令后，高桥君所在的格子 $(R_i,\,C_i)$ 输出在第 $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$ 条指令后，高桥君所在的格子 $(R_i,\,C_i)$ 输出在第 $i$ 行。 > $R_1$ $C_1$ > $R_2$ $C_2$ > $\vdots$ > $R_Q$ $C_Q$

### 数据范围 - $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)$ - 对所有 $i=1,2,\ldots,N$，$(r_\mathrm{s},\,c_\mathrm{s}) \neq (r_i,\,c_i)$ - $1 \leq Q \leq 2 \times 10^5$ - $d_i$ 是 `L`、`R`、`U`、`D` 之一 - $1 \leq l_i \leq 10^9$ - 除 $d_i$ 外，所有输入均为整数 ### 样例解释 1 给定的网格和高桥君的初始位置如下。这里，`#` 表示墙，`T` 表示高桥君，`.` 表示其他格子。 ``` ...#. .#... ..... ...T. ..#.. ``` 对于第 $1$ 条指令，高桥君向左移动 $2$ 格，位置变为 $(4,\,2)$： ``` ...#. .#... ..... .T... ..#.. ``` 对于第 $2$ 条指令，高桥君向上移动 $1$ 格后，因下一个位置是墙，后续 $2$ 次“什么也不做”，最终位置为 $(3,\,2)$： ``` ...#. .#... .T... ..... ..#.. ``` 对于第 $3$ 条指令，高桥君向左移动 $1$ 格后，因下一个位置不存在，后续 $1$ 次“什么也不做”，最终位置为 $(3,\,1)$： ``` ...#. .#... T.... ..... ..#.. ``` 对于第 $4$ 条指令，高桥君向右移动 $4$ 格，最终位置为 $(3,\,5)$： ``` ...#. .#... ....T ..... ..#.. ``` 由 ChatGPT 4.1 翻译