著名厨师 Clémentine Debœuf 正在为她的高级餐厅购买新餐桌。她决定追随最新潮流，选择一款带有大量、宽大且精致装饰的大型餐桌。然而，她需要确保这些装饰不会妨碍餐盘的完美摆放。

装饰品减少了服务员可以安全放置餐盘的平坦桌面面积。Clémentine 希望确保所有餐盘都能放置在桌面上足够大的安全区域内，即不与任何装饰品重叠。给定所有装饰区域的尺寸和位置，Clémentine 请你告诉她这些装饰品对可放置餐盘的位置有何影响。

餐桌是一个宽度为 $X$、长度为 $Y$ 的矩形（单位为毫米）。桌面上放置了 $N$ 个装饰品。每个装饰品都位于固定的桌面坐标处，形状为矩形，其边与桌子的边平行。当然，这些区域互不重叠，但它们可以相互接触。

在 Clémentine 的餐厅里，所有 $D$ 个餐盘都是矩形的，并以预定的方向放置，其边与桌子的边平行。服务员具有毫米级的精度：他们会将餐盘放置在整数毫米坐标处，且餐盘的边与桌子的边平行。餐盘不应与任何装饰区域重叠（但可以接触其边缘）。给定一组由其尺寸描述的餐盘，你的任务是对于每一个餐盘，计算它在桌面上可以安全放置的（整数）位置数量。注意：桌面上一次只供应一个餐盘；这意味着你不需要担心餐盘之间可能重叠的问题，你可以独立地计算每个餐盘的位置。

输入格式

输入包含多行，每行由空格分隔的整数组成： 第一行包含整数 $X, Y, N$ 和 $D$； 接下来的 $N$ 行，每行包含一个装饰品的坐标，由四个整数 $x, x', y$ 和 $y'$ 表示，其中 $0 \leqslant x < x' \leqslant X$ 且 $0 \leqslant y < y' \leqslant Y$，描述了一个跨越点 $(x, y)$ 到点 $(x', y')$ 的装饰品； * 接下来的 $D$ 行，每行包含餐盘的宽度 $x$ 和长度 $y$，由两个整数表示，其中 $0 < x \leqslant X$ 且 $0 < y \leqslant Y$。

数据范围

• $1 \leqslant X, Y \leqslant 2\,000$；
• $0 \leqslant N \leqslant 1\,000\,000$；
• $1 \leqslant D \leqslant 100\,000$。

输出格式

输出 $D$ 行，每行包含每个餐盘的有效整数位置数量。

样例

样例输入 1

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
1
0
13
5
1
0
0
26