分数: 400 点
问题陈述
有一个网格 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 说明。
约束
- 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第行应包含正方形 (R_i, C_i) 高桥跟随第一个之后会在哪里 i 指令,格式如下:
R_1 C_1 R_2 C_2 \vdots R_Q C_Q
示例输入 1
5 5 4 4 3 5 3 2 2 1 4 4 L 2 U 3 L 2 R 4
示例输出 1
4 2 3 2 3 1 3 5
给定的网格和高桥的初始位置如下,其中 # 表示有墙的正方形, T 高桥所在的广场,以及 . 其他方块:
...#. .#... ..... ...T. ..#..
鉴于 1-st指令,高桥出招 2 向左方格,最终以方格结束 (4, 2) 如下:
...#. .#... ..... .T... ..#..
鉴于 2-nd指令,高桥第一个动作 1 向上方格,然后他“什么都不做”两次,因为他方向上的相邻方格有一堵墙。 结果,他最终陷入了困境 (3, 2) 如下:
...#. .#... .T... ..... ..#..
鉴于 3-rd指令,高桥先走 1 向左方格,然后他“什么也不做”一次,因为在他的方向上没有方格。 结果,他最终陷入了困境 (3, 1) 如下:
...#. .#... T.... ..... ..#..
鉴于 4第指令,高桥出招 4 向右方格,以方格结束 (3, 5) 如下:
...#. .#... ....T ..... ..#..
示例输入 2
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
示例输出 2
6 3 5 3 5 1 6 1 4 1 6 1 4 1 4 2 4 1 5 1