F. 机器人

题目描述

给定一个 $H \times W$ 的矩阵，矩阵上有 $N$ 个障碍物，第 $i$ 个障碍物的位置是 $r_i$ 行（从上往下数）$c_i$ 列（从左往右数）。

有一个机器人，从 $r_s\ c_s$ 出发，依次接受 $Q$ 个指令，第 $i$ 个指令为向 $d_i$（UDLR）的方向走 $l_i$ 步，如果遇到障碍物或者边界则不继续前行。

请你输出每一个指令执行之后，机器人的位置。

输入格式

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

输出格式

输出 $Q$ 行答案，第 $i$ 行表示经过指令 $i$ 之后，机器人的位置 $R_i\ C_i$。

样例

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

2 3
2 5
5 5
5 3

数据范围与提示

• $1 \le H, W \le 10^9$
• $1 \le N, Q \le 2 \times 10^5$
• $1 \le r_i \le H,\ 1 \le c_i \le W$
• $1 \le r_s \le H,\ 1 \le c_s \le W$
• $d_i \in \{U, D, L, R\}$
• $1 \le l_i \le 10^9$