002 - 韓流ハゲ

問題

韓国製ThinkPadを買わされた韓流ハゲ(以下ハゲ)がいた。

ハゲはその怒りからか、浜松市内に爆弾を仕掛けてしまった。

爆弾には1〜9までの威力があり、爆発するとその威力に応じて周囲を更地に変えてしまう。

爆弾爆発後、ハゲはさすがに申し訳なく思ったのか、更地に変えてしまったところにN本の新しい道路を作ろうと考えた。

新しい道路のスタート地点からゴール地点に更地のみを辿って行くことができれば、その道路を作ることができる。

更地を辿るときは、上、下、右、左の四方向にしか進むことができない。

N本の新しい道路について、その道路を作ることができるならyes、できないならnoを出力しなさい。

大きさH(縦) x W(横)の浜松市内のマップが与えられ、建物や道路は '#' 、爆弾は '1' 〜 '9' であらわされる。

数字は爆弾の威力である。爆弾はその威力に応じ、爆弾を中心とした周囲Kマスを更地に変える。(1なら周囲1マス、9なら周囲9マス)

入力

1行目に、浜松市内のマップの縦と横の大きさH, Wが与えられます。

2行目からH + 1行目に、浜松市内のマップの情報が与えられます。

H + 2行目に、新しく作る道路の本数Nが与えられます。

H + 3行目からN行にわたって道路のスタート地点とゴール地点の座標が与えられます。(マップの左上隅の座標を (0, 0) とします)

H  W
C0,0C0,1 . . . C0,W-1
C1,0C1,1 . . . C1,W-1
.
.
.
CH-1,0CH-1,1 . . . CH-1,W-1
N
Sx0  Sy0  Gx0  Gy0
Sx1  Sy1  Gx1  Gy1
.
.
.
SxN-1  SyN-1  GxN-1  GyN-1

出力

新しい道路が作れるかどうかをそれぞれ "yes" か "no" で出力してください。

制約

• 10 ≤ H ≤ 1000
• 10 ≤ W ≤ 1000
• 1 ≤ N ≤ 10000
• 0 ≤ Sy, Gy ≤ H - 1
• 0 ≤ Sx, Gx ≤ W - 1
• マップに含まれる、爆弾の数は (H x W x 0.2) 個を超えません。

入出力例

入力例1

20 20
####################
####################
####################
####################
####################
########3###########
####################
##################6#
####################
####################
####################
####################
####################
####################
#1##################
####################
#############4######
####################
####################
####################
10
10 8 6 13
1 7 19 15
14 15 3 2
6 13 9 5
19 14 1 14
3 4 13 7
10 7 7 4
10 19 10 7
15 7 12 14
8 13 10 16

出力例1

no
no
no
no
no
no
yes
yes
yes
no

参考

入力例1の爆弾爆発前(左)と爆発後(右)のマップ
(更地は '.' であらわされています)

####################    ####################
####################    ############........
####################    #####...............
####################    #####...............
####################    #####...............
########3###########    #####...............
####################    #####...............
##################6#    #####...............
####################    #####...............
####################    ############........
####################    ############........
####################    ############........
####################    #########...........
####################    ...######...........
#1##################    ...######.........##
####################    ...######.........##
#############4######    #########.........##
####################    #########.........##
####################    #########.........##
####################    #########.........##