AT_abc391_d.[ABC391D] Gravity

存在一个 $10^9$ 行 $W$ 列的网格。将左数第 $x$ 列、下数第 $y$ 行的单元格记为 $(x,y)$。

有 $N$ 个方块。每个方块是 $1 \times 1$ 的正方形，方块 $i$（$1 \leq i \leq N$）在时刻 $0$ 时位于单元格 $(X_i,Y_i)$。

在时刻 $t=1,2,\dots,10^{100}$ 时，按照以下规则移动方块：

1. 若网格下数第 $1$ 行所有列均被方块填满，则消除下数第 $1$ 行的所有方块。
2. 对于剩余的方块，从下往上的顺序依次进行以下操作：
   • 若方块位于最底行，或其下方相邻单元格已有方块，则不进行任何操作。
   • 否则，将方块移动到下方相邻单元格。

给定 $Q$ 个询问。对于第 $j$ 个询问（$1 \leq j \leq Q$），请判断在时刻 $T_j+0.5$ 时方块 $A_j$ 是否存在。

输入通过标准输入按以下格式给出：

$N$ $W$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$
$Q$
$T_1$ $A_1$
$T_2$ $A_2$
$\vdots$
$T_Q$ $A_Q$

输出 $Q$ 行。第 $i$ 行输出 Yes（若时刻 $T_i+0.5$ 时方块 $A_i$ 存在）或 No（若不存在）。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq W \leq N$
• $1 \leq X_i \leq W$
• $1 \leq Y_i \leq 10^9$
• $i \neq j$ 时 $(X_i,Y_i) \neq (X_j,Y_j)$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq T_j \leq 10^9$
• $1 \leq A_j \leq N$
• 输入均为整数

样例解释 1

方块位置变化如下图所示：

• 询问 $1$：时刻 $1.5$ 时方块 $1$ 存在，输出 Yes。
• 询问 $2$：时刻 $1.5$ 时方块 $2$ 存在，输出 Yes。
• 询问 $3$：方块 $3$ 在时刻 $2$ 被消除，因此时刻 $2.5$ 时不存在，输出 No。

翻译由 DeepSeek R1 完成