/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
あなたはスライドパズルで遊んでいます。このパズルは、縦 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を出力する。
制約
- 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 の正方形の領域には、障害物が存在しない。
入力
入力は以下の形式で与えられる。ただし、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
5 2 5 ..#.. ..... ####. ..... #.... 1 1 1 4 1 1 1 1 1 4 4 2 4 2 4 4 4 2 4 3
出力例 1
No Yes No Yes Yes
例えば 4 番目のクエリは、駒を右方向に 2 マス分平行移動させることで、途中で障害物と重なることなく移動させることができます。 一方 1 番目のクエリでは、障害物が邪魔となって目的地まで駒を移動させることができません。
入力例 2
7 3 5 ....... ....... ...#... ....... ....... ..#.... ......# 2 1 1 1 1 1 1 5 3 1 4 4 5 4 1 5 3 1 3 5
出力例 2
Yes No No Yes No