背景

翻译来源：loj #5710. 「NordicOI 2026」Backrooms。

2s，1024MB。

Subtask 0 为样例。

题目描述

巫师 Harry 喜欢烘焙。有一天，他发现了一个咒语，可以把他传送到「后台」（Backrooms，这个双关语只在瑞典语中成立），他感到非常高兴。然而，当他使用这个咒语时，他没有被传送到烘焙店，而是被传送到了一个无限大的网格中。网格中的每个单元格要么是空闲的，要么是堵塞的。在网格中，你可以向上下左右四个方向移动到相邻且未堵塞的单元格。走了一会儿后，他注意到堵塞单元格的分布模式是周期性的。更准确地说，存在一个 $R \times C$ 的图案在无限重复。具体工作方式见下图。

:::align{center} :::

为了逃离，他需要到达网格中的某个单元格。然而，他的传送魔法生疏了，所以他会问你 $Q$ 个问题，格式如下：「如果我传送到单元格 $(s_x, s_y)$，我能走到单元格 $(g_x, g_y)$ 吗？」

输入格式

第一行包含两个整数 $R$ 和 $C$ $(1 \leq R, C \leq 1000)$，表示网格的行数和列数。

接下来的 $R$ 行，每行包含一个长度为 $C$ 的字符串，由字符 . 和 # 组成。这些是网格的行。字符 # 表示该单元格已堵塞，字符 . 表示该单元格为空闲。

随后的一行包含整数 $Q$ $(1 \leq Q \leq 10^5)$，表示你需要回答的问题数量。

接下来的 $Q$ 行，每行包含四个整数 $s_x, s_y, g_x, g_y$ $(0 \leq s_x, s_y, g_x, g_y \leq 10^{12})$，表示问题的坐标。保证这些坐标处的单元格均未堵塞。

输出格式

对于每个问题，如果 Harry 能从单元格 $(s_x, s_y)$ 走到单元格 $(g_x, g_y)$，则输出 Yes，否则输出 No。

3 3
#.#
.#.
..#
5
2 4 4 3
0 0 2 1
0 0 0 0
900000002 900000004 900000004 900000003
2 1 1 2

Yes
No
Yes
Yes
No

提示

评分

详细子任务附加限制及分值如下表所示：

样例解释

• 问题 $1$：Harry 从 $(2,4)$ 出发，想要移动到 $(4,3)$。为此，他可以向右、向下、向右移动。
• 问题 $2$：起点和终点被墙壁隔开，因此答案为 No。
• 问题 $3$：Harry 已经站在终点，所以他瞬间完成了任务。
• 问题 $4$：即使在非常远的地方，网格仍在继续。答案最终为 Yes。
• 问题 $5$：同样地，起点和终点被墙壁隔开。