题目描述

有一个 $H\times W$ 的网格，其中有 $N$ 个位置有障碍物。

最初高桥在 $(r_\mathrm{s}, c_\mathrm{s})$ 方格。

现在有 $Q$ 个问题，每个问题由一个字符 $l_i$ 和一个整数 $d_i$ 构成。

• $l_i=L$，意思向左前进 $d_i$ 格。
• $l_i=R$，意思向右前进 $d_i$ 格。
• $l_i=U$，意思向上前进 $d_i$ 格。
• $l_i=D$，意思向下前进 $d_i$ 格。

在移动的过程中遇到以下两种情况会停止前进：

• 下一个格子是一个障碍物。
• 下一个格子会离开网格的范围。例如移动到第 $H+1$ 行。

现在每次询问，你需要回答移动后所处的位置。

输入格式

第一行输入四个整数分别是 $H$ $W$ $r_\mathrm{s}$ $c_\mathrm{s}$

第二行输入一个整数 $N$

接下来 $N$ 行，每行两个整数 $r$ $c$ 代表这里有一个障碍物

然后输入一个整数 $Q$

接下来 $Q$ 行，每行两个整数 $d$ $l$ 代表一种移动策略。

输出格式

输出一共输出 $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

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 \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$ 之外的所有输入值均为整数。

样例 1 解释

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

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

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

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

根据第 $2$ 个指令，高桥首先向上移动了 $1$ 个方格，然后他无法继续移动，因为他所在方向的相邻方格有一堵墙。结果，他最终下在了 $(3, 2)$ 位置，如下所示：

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

给定第 $3$ 个指令，高桥首先向左移动 $1$ 个方格，然后他无法移动，因为继续移动就会离开网格范围。结果，他最终下到了如下所示的 $(3, 1)$ 格：

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

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

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