Problem Description

You are playing a sliding puzzle. This puzzle uses a board consisting of a square grid of $N$ rows and $N$ columns. The cell at the $i$-th row from the top and the $j$-th column from the left is represented as $(i,\ j)$. Some cells on the board have obstacles placed on them (it is also possible that none are placed). Additionally, the piece you slide and move on this board is a square that occupies $K$ rows and $K$ columns.

This piece can be placed on any cell where it does not overlap with an obstacle, and it can be moved up, down, left, or right without any part of it going out of the board or overlapping with an obstacle.

You are given $Q$ queries, and you need to process each query as follows:

• Two cells $(r_1,\ c_1)$ and $(r_2,\ c_2)$ are given. Starting with the top-left corner of the piece at $(r_1,\ c_1)$, determine if it is possible to reach the state where the top-left corner of the piece is at $(r_2,\ c_2)$ by sliding only. If possible, output Yes; otherwise, output No.

Input Format

The input is given in the following format, where $ s_{ij} $ $(1 \leq i, j \leq N)$ is . if there is no obstacle at $(i,\ j)$ and # if there is an obstacle at $(i,\ j)$. Also, $ r_{i1} $, $ c_{i1} $, $ r_{i2} $, $ c_{i2} $ $(1 \leq i \leq Q)$ represent $ r_1 $, $ c_1 $, $ r_2 $, $ c_2 $ given in the $i$-th query, respectively.

$ 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} $

Output Format

Output the result of the $i$-th query ($1 \leq i \leq Q$) on the $i$-th line.

Sample Input and Output

Sample Input #1

5 2 5
..#..
.....
####.
.....
#....
1 1 1 4
1 1 1 1
1 4 4 2
4 2 4 4
4 2 4 3

Sample Output #1

No
Yes
No
Yes
Yes

Sample Input #2

7 3 5
.......
.......
...#...
.......
.......
..#....
......#
2 1 1 1
1 1 1 5
3 1 4 4
5 4 1 5
3 1 3 5

Sample Output #2

Yes
No
No
Yes
No

Notes/Hints

Constraints

• $1 \leq N \leq 1000$
• $1 \leq K \leq N$
• $ K $ is an integer.
• $1 \leq Q \leq 10^5$
• $ s_{ij} $ $(1 \leq i, j \leq N)$ is either . or #.
• $1 \leq r_{i1}, c_{i1}, r_{i2}, c_{i2} \leq N-K+1$ $(1 \leq i \leq Q)$
• For each query, the $K \times K$ square with the top-left corner at $(r_1,\ c_1)$ and the $K \times K$ square with the top-left corner at $(r_2,\ c_2)$ do not contain any obstacles.

Sample Explanation 1

For example, in the 4th query, the piece can be moved 2 cells to the right without overlapping any obstacles. On the other hand, in the 1st query, the piece cannot be moved to the destination due to obstacles blocking the way.

见题面 Input 部分

见题面 Output 部分