问题描述

你正在玩滑块拼图。这个拼图使用一个由 $N$ 行、$N$ 列的正方形方格组成的盘。盘中的每个方格可以用 $(i, j)$ 表示，其中 $i$ 是行数，$j$ 是列数。在盘上的某些方格上可能放有障碍物（也可能没有放任何障碍物）。拼图块是一个占据 $K$ 行 $K$ 列的正方形区域。

拼图块可以放置在没有障碍物的方格上，并且可以沿着上下左右四个方向进行平行移动，但不能超出盘的边界，也不能与障碍物重叠。

给定以下查询，请处理每个查询：

• 给定两个方格 $(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}$

输出

对于每个查询，输出对应的处理结果。

示例 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

例如，第四个查询可以将拼图块向右移动两格，而不与障碍物重叠。然而，第一个查询中的障碍物会妨碍将拼图块移动到目的地。

示例 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