配点 : $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$

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

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
.....
..#..

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

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