说明

著名厨师 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$ 行，每行包含对应菜肴的有效整数位置数量。

7 5 3 9
1 2 0 1
5 7 2 5
0 1 2 4
7 1
3 5
5 3
2 2
3 3
4 4
4 5
6 2
1 1

1
1
0
13
5
1
0
0
26

提示

样例解释

:::align{center}

:::

数据范围

• $1 \leq X, Y \leq 2000$；
• $0 \leq N \leq 1\,000\,000$；
• $1 \leq D \leq 100\,000$。

翻译由 DeepSeek 完成