問題文

吹雪の中、一人snowrate君は雪に覆われた縦 $H$ 、横 $W$ の盤面上で、サクサクと音を踏みしめながら歩いています。ここで、座標 $(i,j)$ は上から $i$ 番目、左から $j$ 番目のマスを表します。

snowrate君が現在いる座標を $(y,x)$ で表すことにします。今、snowrate君は $(y,x)=(1,1)$ に立っており、下方向を向いています。この盤面上には $N$ 個の看板があり、その各看板には上方向を表す U 、下方向を表す D 、左方向を表す L 、右方向を表す R の、いずれか一つの文字 $d$ が書かれています。
また看板のあるマスにたどり着いた後、看板に書いてる文字に従って以下のように移動します。

• $d=$ U のとき: $(y-1,x)$ に進む
• $d=$ D のとき: $(y+1,x)$ に進む
• $d=$ L のとき: $(y,x-1)$ に進む
• $d=$ R のとき: $(y,x+1)$ に進む

snowrate君は純粋なのでその看板に書かれたことに従って、他の看板があるマスに行くまでその方向を保ち、歩き続けます。看板のあるマスの座標はそれぞれ $(h_1,w_1),(h_2,w_2),...(h_N,w_N)$ に位置しています。またsnowrate君は、次の移動で止まるマスが盤面の外であるか、既に歩いたマスを再び通過すると、そのマスで移動を終えます。

この移動が終わった後、以下のような質問が $Q$ 個配られるので順に答えてください。

• $i\ (1\le i\le Q)$ 個目の質問において、snowrate君は $(A_i,B_i)$ を通過したか判定せよ

入力・制約

・$2\le H,W\le 3000$
・$1\le N\le \min (HW,10^4)$
・$1\le h_k\le H\ (1\le k\le N)$
・$1\le w_k\le W$
・$d_k$ は U , D , L , R のいずれかである
・$1\le Q\le 5\times 10^4$
・$1\le A_i\le H$
・$1\le B_i\le W$
・看板は同じマスに $2$ 個以上置かれない

出力

$Q$ 行出力せよ。$i$ 行目には $i$ 個目の質問の答えを出力せよ。
そのとき、そのマスを歩くことがあるなら Yes 、ないなら No を出力せよ。

入出力例

3 3 1
3 1 R
1
3 2

Yes

$(1,1),(2,1),(3,1)$ と順に移動した時点で R が書かれた看板のマスに止まるので、次の移動では右向きに移動します。
すると方向を切り替えた後で $(3,1),(3,2),(3,3)$ の順で移動しますが、その次の移動でsnowrate君は盤面の外に行ってしまうので $(3,3)$ で静止し、移動を終えます。

よってsnowrate君は $(3,2)$ を通過するので、Yes を出力します。

4 5 3
2 3 R
1 5 L
2 4 D
2
2 4
4 5

No
No

$(1,1),(2,1),(3,1),(4,1)$ を歩いた時点で静止します。よって $2$ 個の質問ともに答えは No です。

2 2 2
1 2 R
2 2 U
3
1 1
1 2
2 1

Yes
No
Yes

看板が置かれている座標が与えられることもあります。

2 2 2
1 1 R
2 2 U
3
1 1
1 2
2 1

Yes
Yes
No

snowrate君が最初にいる位置に看板が置かれていることもあります。