题目描述

给定一个 $N$ 行 $M$ 列的网格。从上往下第 $i$ 行中，从左往右第 $L_i$ 列到第 $R_i$ 列的格子被涂成黑色，其余格子被涂成白色。

给定 $Q$ 个询问。对每个询问，回答下面的问题。

• 给定整数 $A,B,C,D$。求从上往下第 $A$ 行到第 $B$ 行、从左往右第 $C$ 列到第 $D$ 列的矩形区域内黑格的数量。

输入格式

输入按以下格式从标准输入读入：

• $N$ $M$ $Q$
• $L_1$ $R_1$
• $L_2$ $R_2$
• $\vdots$
• $L_N$ $R_N$
• $\mathrm{query}_1$
• $\vdots$
• $\mathrm{query}_Q$

每个询问 $\mathrm{query}_i ~ (1 \le i \le Q)$ 按以下形式给出：

• $A$ $B$ $C$ $D$

输出格式

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

3 6 3
2 4
1 1
4 6
1 2 1 4
2 3 3 6
1 1 5 6

4
3
0

上方给出了黑格的位置。第 $1$ 个询问求左上角蓝色矩形内黑格的数量，第 $2$ 个询问求右下角红色矩形内黑格的数量，第 $3$ 个询问求右上角绿色矩形内黑格的数量。

因此，分别输出 $4, 3, 0$。

10 20 12
3 8
1 4
12 19
5 14
2 2
9 17
1 20
6 11
16 20
7 7
2 8 4 15
6 10 1 9
3 4 1 4
1 10 1 20
4 9 10 18
5 5 1 20
1 6 8 8
8 10 13 20
2 7 1 5
6 9 6 16
3 10 18 20
7 10 7 12

40
15
0
70
27
1
2
5
11
26
8
12

数据范围

• $1 \le N,M,Q \le 2\times10^5$

• $1 \le L_i \le R_i \le M$

• 对每个询问，$1 \le A \le B \le N$。

• 对每个询问，$1 \le C \le D \le M$。

• 所有输入值均为整数。

• 来源：AtCoder ABC 477 F

子任务设置

• 子任务 1（30 分）：$N,M,Q \le 200$。
• 子任务 2（30 分）：$N,M \le 2000$ 且 $Q \le 2\times10^5$。
• 子任务 3（40 分）：无特殊限制。