660 - メロンパン2期

時間制限 1 秒 / メモリ制限 512 MB / 得点 15 / Writer ei1333 / x 2 / 統計 /


TLE
1sec
MLE
512MB
得点
15

問題

サターニャさんが住む街は HW 列のマスに区切られた長方形の形で表されます。

それぞれのマスは, 以下の文字で表されいずれかの意味を持ちます。

  • '.': 道である。
  • '#': 障害物である。

サターニャさんは, 毎日高校から家にメロンパンを持って帰宅します。 具体的には, 高校から家に辺で隣接するマスを通って移動します。このとき障害物マスに入ることはできません。また毎日新しいメロンパンを購入して, それを持って帰宅します。

サターニャさんは帰宅はしますが, 馬や鹿のような思考能力を持つ(ガヴリールさんからそう教わったらしい)ので必ずしも最短経路を通って移動するとは限りません。

サターニャさん「犬、こわい、やめてっ!」 サターニャさんは, 帰宅時によく犬にメロンパンがとられるので悩んでいました。
そんなある日, 魔界通販で「高校と家の位置を可変にする装置(そのまま)」というのが売られていたので買いました。説明書によると, 装置を使用すると高校と家の位置が無作為に他の道マスに移動するようです。 サターニャさんはこれを毎日使って犬を惑わせることにしました。(悪魔的ね!)

N 日間のサターニャさんの帰宅を考えます。 犬は天才なので, 装置を使用することによって高校と家の位置がどこに存在するか把握しています。 i 日目には高校が AiBi 列目, 家が CiDi 列目にあります。 また, 移動しうる高校と家の位置はもともと道マスで, 移動後にそのマスはもとの道マスに戻ることが分かっています。

犬はサターニャさんが持っているメロンパンを得るために, それぞれの日について道マスから 1 マスを選んでそのマスで待ち伏せすることに決めました。学校と家はサターニャさんによって掌握されているので, それらのマスを選ぶことはできないので注意してください。

犬は, サターニャさんが必ず通過する道マスで待ち伏せしたいです。 それぞれの日について, このようなマスがあるか判定してください。

入力

H W
S1,1S1,2...S1,W
S2,1S2,2...S2,W
:
SH,1SH,2...SH,W
N
A1 B1 C1 D1
A2 B2 C2 D2
:
AN BN CN DN

1 行目に長方形の行数 H(1 ≤ H300), 列数 W(1 ≤ W300) が与えられます。

つづく H 行には, それぞれ W 個からなる文字列が与えられます。 ij 列目の文字 Si,j('.', '#' のいずれか) は, サターニャさんが住む街の ij 列目のマスが Si,j の意味を持つことを表します。

つづく 1 行に, 日数 N(1 ≤ N ≤ 100 000) が与えられます。

つづく N 行にかけて, それぞれの日の高校と家の状態が与えられます。 このうち i 行目の 4 つの値 Ai, Bi, Ci, Di(1 ≤ Ai, CiH, 1 ≤ Bi, DiW) は, i 日目にサターニャさんの高校が AiBi 列目にあって, サターニャさんの家が CiDi 列目にあることを表します。 また SAi,BiSCi,Di は共に '.' で, (Ai, Bi) ≠ (Ci, Di) です。

与えられる街では, どの道マスから他のすべての道マスに到達できることが保証されています。

出力

出力は N 行からなります。 i 行目には, i 日目の状態で条件を満たす道マスが存在するとき yes, 存在しないとき no を出力してください。

入出力例

入力例 1

3 3
..#
#.#
#..
3
1 1 3 3
2 2 3 2
2 2 3 3

出力例 1

yes
no
yes

サターニャさんの高校の位置を 'S', 家の位置を 'G' で表すこととします。

1 日目の状態は以下です。

S.#
#.#
#.G

このとき, 2 列目のどの道マスを選んでも必ずサターニャさんが通過します。

2 日目の状態は以下です。

..#
#S#
#G.

このとき, 高校から家へ直接移動することが出来ます。高校と家は掌握されていることに注意してください。

3 日目の状態は以下です。

..#
#S#
#.G

3 行 2 列目の道マスについて, 必ずサターニャが通過します。

入力例 2

3 4
....
....
....
3
1 1 3 3
2 2 3 4
2 2 3 3

出力例 2

no
no
no

どの位置に高校や家が存在しても条件を満たす道マスが存在しないことがあります。

2期あるといいなぁ(難民なので)