P16379 [NordicOI 2026] Backrooms 后台

翻译来源：loj [#5710. 「NordicOI 2026」Backrooms](https://loj.ac/p/5710)。 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`。

### 评分 详细子任务附加限制及分值如下表所示： | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $7$ | $R, C \leq 2$, $Q \leq 5$, $s_x, s_y, g_x, g_y \leq 500$ | | $2$ | $4$ | $R, C, Q \leq 5$, $s_x, s_y, g_x, g_y \leq 500$ | | $3$ | $8$ | $R, C, Q \leq 5$, $s_x, s_y, g_x, g_y \leq 10^5$ | | $4$ | $25$ | $R, C, Q \leq 5$ | | $5$ | $15$ | $R, C \leq 5$ | | $6$ | $21$ | $R, C \leq 25$ | | $7$ | $20$ | 无附加限制 | ### 样例解释 * 问题 $1$：Harry 从 $(2,4)$ 出发，想要移动到 $(4,3)$。为此，他可以向右、向下、向右移动。 * 问题 $2$：起点和终点被墙壁隔开，因此答案为 `No`。 * 问题 $3$：Harry 已经站在终点，所以他瞬间完成了任务。 * 问题 $4$：即使在非常远的地方，网格仍在继续。答案最终为 `Yes`。 * 问题 $5$：同样地，起点和终点被墙壁隔开。