AT_pakencamp_2025_day2_e Grand Paken

在パケン王国的一个角落，有一座名为グランド・パケン的建筑。该建筑为一个高 $H$ 行、宽 $W$ 列的矩形，并被划分为 $1 \times 1$ 的正方形区块。从上到下第 $a$ 行、从左到右第 $b$ 列的区块记作 $(a,b)$。グランド・パケン内共有 $N$ 个出口，第 $i$ 个出口位于区块 $(A_{i}, B_{i})$。 --- 有一天，グランド・パケン发生了火灾。火灾共有 $M$ 个起点，第 $i$ 个起火点位于 $(C_i, D_i)$。所有火灾在时刻 $0$ 同时发生。火灾每经过 $1$ 单位时间，会蔓延到上下左右相邻的区块。对于区块 $(x, y)$，如果它到任意一个起火点的曼哈顿距离不超过 $t$，那么在时刻 $t$，它正处于燃烧状态。需要注意的是，区块一旦开始燃烧，将会持续燃烧。 --- 作为被派遣的救援队员，你需要回答关于被困人员的 $Q$ 个询问。对于第 $i$ 个询问，有如下情况： - 在时刻 $0$，有人在区块 $(X_{i}, Y_{i})$。 - 每经过 $1$ 单位时间，人员可以移动到上、下、左、右相邻的区块。 - 人员只有在当前区块还未开始燃烧的所有时刻，才能进行行动。 也就是说，人员要在时刻 $t$ 到达某个区块，该区块的燃烧开始时刻必须严格大于 $t$。在这个条件下，判断该人员能否到达任意一个有出口的区块。如果可以到达，输出 `Yes`，否则输出 `No`。

输入通过标准输入给出，格式如下： > $ H $ $ W $ $ N $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_N $ $ B_N $ $ M $ $ C_1 $ $ D_1 $ $ \vdots $ $ C_M $ $ D_M $ $ Q $ $ X_1 $ $ Y_1 $ $ \vdots $ $ X_Q $ $ Y_Q $

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

### 子任务 1.（$10$ 分）$H \times W \leq 300$ 2.（$20$ 分）$H, W \leq 300$ 3.（$30$ 分）$H, W \leq 2000$ 4.（$40$ 分）无额外限制 ### 样例解释 1 对于第 $1$、$2$ 个询问，无论采取何种移动方式，均无法满足条件到达出口。 对于第 $3$ 个询问，人员在时刻 $0$ 位于 $(1, 5)$。若在时刻 $1$ 移动到 $(2, 5)$，则可满足条件到达出口区块。$(2, 5)$ 从时刻 $3$ 开始燃烧。 # 数据范围 - $1 \le H, W \le 2 \times 10^5$ - $1 \le N, M, Q \le 2 \times 10^5$ - $1 \le A_i \le H$ - $1 \le B_i \le W$ - $1 \le C_i \le H$ - $1 \le D_i \le W$ - $1 \le X_i \le H$ - $1 \le Y_i \le W$ - 所有输入均为整数。 由 ChatGPT 5 翻译