問題
韓国製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###### #########.........## #################### #########.........## #################### #########.........## #################### #########.........##