P15219 [SWERC 2017] Table

著名厨师 Clémentine Debeuf 正在为她高级餐厅购买新桌子。她决定选择最新的潮流款式：一种带有众多宽阔而精致装饰的大号型号。然而，她需要确保这些装饰不会妨碍菜肴完美协调的摆放。 装饰减少了服务员可以安全放置菜肴的平整桌面区域。Clémentine 想要确保所有菜肴都能在桌面上足够大的安全区域内找到位置，即不与任何装饰重叠。给定所有装饰区域的尺寸和位置，Clémentine 请你告诉她这些装饰对菜肴可放置位置的影响。 桌子是一个宽度为 $X$、长度为 $Y$ 的矩形，单位为毫米。桌面上放置了 $N$ 个装饰。每个装饰位于固定的桌面坐标上，形状为矩形，其边与桌子边平行。当然，这些区域互不重叠，但可以接触。 在 Clémentine 的餐厅中，所有 $D$ 个菜肴都是矩形，并以预定的方向放置，其边与桌子边平行。服务员有毫米级精度：他们会将菜肴放在整数毫米坐标上，且其边与桌子边平行。菜肴不能与任何装饰区域重叠（但可以接触其边缘）。给定一个描述菜肴尺寸的列表，你的任务是告诉每个菜肴可以安全放置在桌子上的（整数）位置数量。注意：桌子上一次只上一道菜；这意味着你不需要担心菜肴之间可能重叠，你可以独立计算每个菜肴的位置数量。

输入包含若干行，每行由空格分隔的整数组成： - 第一行包含整数 $X$, $Y$, $N$, 和 $D$； - 接下来的 $N$ 行每行包含一个装饰的坐标，即四个整数 $x$, $x'$, $y$, $y'$，满足 $0 \leq x < x' \leq X$ 且 $0 \leq y < y' \leq Y$，描述一个从点 $(x, y)$ 到点 $(x', y')$ 的装饰区域； - 接下来的 $D$ 行每行包含两个整数 $x$ 和 $y$，表示菜肴的宽度和长度，满足 $0 < x \leq X$ 且 $0 < y \leq Y$。

输出 $D$ 行，每行包含对应菜肴的有效整数位置数量。

#### 样例解释 :::align{center}  ::: ### 数据范围 - $1 \leq X, Y \leq 2000$； - $0 \leq N \leq 1\,000\,000$； - $1 \leq D \leq 100\,000$。 翻译由 DeepSeek 完成