题目描述

$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$ 番目までの指示を実行した直後に高橋君がいるマスを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

题目大意

你有一个 $h \times w$ 的矩阵，矩阵上有 $N$ 个障碍物，现在给你 $Q$ 次询问，问向 $R_i$ 的方向走 $C_i$ 步到哪里了。 前一步能影响后一步，障碍物不能越过，不能走出边界

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

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

提示

制約

• $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$ 以外の入力値は整数

Sample Explanation 1

与えられるグリッドと高橋君の初期位置は下記の通りです。 ここで、# は壁のマスを、T は高橋君がいるマスを表し、. がその他のマスを表します。 ...#. .#... ..... ...T. ..#.. $1$ つ目の指示に対して高橋君は、左に $2$ マス移動し、高橋君の位置は下記の通り、マス $(4,\ 2)$ になります。 ...#. .#... ..... .T... ..#.. $2$ つ目の指示に対して高橋君は、上に $1$ マスに移動した後、次の移動先が壁であるために「何もしない」を $2$ 回行います。その結果、高橋君の位置は下記の通り、マス $(3,\ 2)$ になります。 ...#. .#... .T... ..... ..#.. $3$ つ目の指示に対して高橋君は、左に $1$ マス移動した後、次の移動先となるマスが存在しないために「何もしない」を $1$ 回行います。その結果、高橋君の位置は下記の通り、マス $(3,\ 1)$ になります。 ...#. .#... T.... ..... ..#.. $4$ つ目の指示に対して高橋君は、右に $4$ マス移動し、高橋君の位置は下記の通り、マス $(3,\ 5)$ になります。 ...#. .#... ....T ..... ..#..