7260: ABC273 —— D - LRUD Instructions
[Creator : ]
Description
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:
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.
Input
The input is given from Standard Input in the following format:
$H\ W r_\mathrm{s}\ rsc_\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$
$H\ W r_\mathrm{s}\ rsc_\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 ii instructions, in the following format:
$R_1\ C_1$
$R_2\ C_2$
$\vdots$
$R_Q\ C_Q$
$R_1\ C_1$
$R_2\ C_2$
$\vdots$
$R_Q\ C_Q$
Constraints
$2≤H,W≤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.
$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.
Sample 1 Input
5 5 4 4
3
5 3
2 2
1 4
4
L 2
U 3
L 2
R 4
Sample 1 Output
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:
Given the 1-st instruction, Takahashi moves 2 squares to the left, ending up in square (4, 2) as follows:
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:
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:
Given the 4-th instruction, Takahashi moves 4 squares to the right, ending up in square (3, 5) as follows:
...#. .#... ..... ...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 2 Input
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 2 Output
6 3
5 3
5 1
6 1
4 1
6 1
4 1
4 2
4 1
5 1