102733: [AtCoder]ABC273 D - LRUD Instructions

Problem Statement

There is a grid with $H$ horizontal rows and $W$ vertical columns. $(i, j)$ denotes the square at the $i$-th row from the top and $j$-th column from the left.
$N$ squares, $(r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N)$, have walls.

Takahashi is initially at square $(r_\mathrm{s}, c_\mathrm{s})$.

$Q$ instructions are given to Takahashi. For $i = 1, 2, \ldots, Q$, the $i$-th instruction is represented by a pair of a character $d_i$ and a positive integer $l_i$. $d_i$ is one of L, R, U, and D, representing the directions of left, right, up, and down, respectively.

Given the $i$-th direction, Takahashi repeats the following action $l_i$ times:

If a square without a wall is adjacent to the current square in the direction represented by $d_i$, move to that square; otherwise, do nothing.

For $i = 1, 2, \ldots, Q$, print the square where Takahashi will be after he follows the first $i$ instructions.

Constraints

• $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)$ for all $i = 1, 2, \ldots, N$.
• $1 \leq Q \leq 2 \times 10^5$
• $d_i$ is one of the characters L, R, U, and D.
• $1 \leq l_i \leq 10^9$
• All values in the input other than $d_i$ are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines. For $i = 1, 2, \ldots, Q$, the $i$-th line should contain the square $(R_i, C_i)$ where Takahashi will be after he follows the first $i$ instructions, in the following format:

$R_1$ $C_1$
$R_2$ $C_2$
$\vdots$
$R_Q$ $C_Q$

Sample Input 1

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

Sample Output 1

4 2
3 2
3 1
3 5

The given grid and the initial position of Takahashi are as follows, where # denotes a square with a wall, T a square where Takahashi is, and . the other squares:

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

Given the $1$-st instruction, Takahashi moves $2$ squares to the left, ending up in square $(4, 2)$ as follows:

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

Given the $2$-nd instruction, Takahashi first moves $1$ square upward, then he "does nothing" twice because the adjacent square in his direction has a wall. As a result, he ends up in square $(3, 2)$ as follows:

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

Given the $3$-rd instruction, Takahashi first moves $1$ square to the left, then he "does nothing" once because there is no square in his direction. As a result, he ends up in square $(3, 1)$ as follows:

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

Given the $4$-th instruction, Takahashi moves $4$ squares to the right, ending up in square $(3, 5)$ as follows:

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

Sample Input 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

Sample Output 2

6 3
5 3
5 1
6 1
4 1
6 1
4 1
4 2
4 1
5 1

问题描述

有一个有$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 = 1, 2, \ldots, Q$，第$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$

样例输入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

给定的网格和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

.....

..#..

样例输入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