AT_bcu30_e スライドパズル

[problemUrl]: https://atcoder.jp/contests/bcu30/tasks/bcu30_e あなたはスライドパズルで遊んでいます。このパズルは、縦 $ N $ 行、横 $ N $ 列の正方形のマスが並んだ盤を使います。盤の上から $ i $ 行目、左から $ j $ 列目のマスは、 $ (i,\ j) $ と表されます。 盤の中のいくつかのマスには障害物が置かれています。($ 1 $ つも置かれていない場合もあります。) また、この盤の上でスライドさせて動かす駒は、盤の縦 $ K $ 行、横 $ K $ 列を占める大きさの正方形です。 この駒は、障害物が置かれているマスに重ならない場所に置くことができ、駒の一部が盤からはみ出したり、障害物と重なることがないように、上下左右の $ 4 $ 方向に平行移動させることができます。 以下のようなクエリが $ Q $ 個与えられるので、それぞれのクエリを処理してください。 - $ 2 $ つのマス $ (r_1,\ c_1) $ と $ (r_2,\ c_2) $ が与えられる。駒の左上が $ (r_1,\ c_1) $ に重なるように置かれている状態から、駒の左上が $ (r_2,\ c_2) $ に重なるように置かれている状態まで、スライドすることだけで到達できるなら `Yes`、到達できないなら `No` を出力する。

入力は以下の形式で与えられる。ただし、$ s_{ij} $ $ (1\ \leq\ i,\ j\ \leq\ N) $ が `.` のときは、盤の $ (i,\ j) $ に障害物が置かれていないことを、 `#` のときは盤の $ (i,\ j) $ に障害物が置かれていることを表す。 また、 $ r_{i1} $, $ c_{i1} $, $ r_{i2} $, $ c_{i2} $ $ (1\ \leq\ i\ \leq\ Q) $はそれぞれ、 $ i $ 番目のクエリで与えられる $ r_1 $, $ c_1 $, $ r_2 $, $ c_2 $ を表す。 > $ N $ $ K $ $ Q $ $ s_{11}s_{12} $ ... $ s_{1N} $ : $ s_{N1}s_{N2} $ ... $ s_{NN} $ $ r_{11} $ $ c_{11} $ $ r_{12} $ $ c_{12} $ : $ r_{Q1} $ $ c_{Q1} $ $ r_{Q2} $ $ c_{Q2} $

$ i $ 行目 $ (1\ \leq\ i\ \leq\ Q) $ に $ i $ 番目のクエリの処理結果を出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 1000 $ - $ 1\ \leq\ K\ \leq\ N $ - $ K $ は整数である。 - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ s_{ij} $ $ (1\ \leq\ i,\ j\ \leq\ N) $ は `.` または `#` である。 - $ 1\ \leq\ r_{i1},\ c_{i1},\ r_{i2},\ c_{i2}\ \leq\ N-K+1 $ $ (1\ \leq\ i\ \leq\ Q) $ - 各クエリにおいて、$ (r_1,\ c_1) $ を左上とする大きさ $ K\ \times\ K $ の正方形および $ (r_2,\ c_2) $ を左上とする大きさ $ K\ \times\ K $ の正方形の領域には、障害物が存在しない。 ### Sample Explanation 1 例えば $ 4 $ 番目のクエリは、駒を右方向に $ 2 $ マス分平行移動させることで、途中で障害物と重なることなく移動させることができます。 一方 $ 1 $ 番目のクエリでは、障害物が邪魔となって目的地まで駒を移動させることができません。