D - LRUD Instructions Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 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)
  • すべての i = 1, 2, \ldots, Nについて、(r_\mathrm{s}, c_\mathrm{s}) \neq (r_i, c_i)
  • 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 つ目の指示に対して高橋君は、左に 2 マス移動し、高橋君の位置は下記の通り、マス (4, 2) になります。

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

2 つ目の指示に対して高橋君は、上に 1 マスに移動した後、次の移動先が壁であるために「何もしない」を 2 回行います。その結果、高橋君の位置は下記の通り、マス (3, 2) になります。

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

3 つ目の指示に対して高橋君は、左に 1 マス移動した後、次の移動先となるマスが存在しないために「何もしない」を 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

Score : 400 points

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