AT_abc477_f.Count Cells in a Window

You are given a grid with $N$ rows and $M$ columns. In the $i$-th row from the top, the squares from the $L_i$-th through $R_i$-th columns from the left are painted black, and the other squares are painted white.

You are given $Q$ queries. For each query, answer the following question.

• You are given integers $A,B,C,D$. Find the number of black squares contained in the rectangular region from the $A$-th through $B$-th rows from the top and from the $C$-th through $D$-th columns from the left.

给你一个 $N$ 行 $M$ 列的网格。在从上往下数第 $i$ 行中，从左往右数第 $L_i$ 列到第 $R_i$ 列（含端点）的格子被涂成黑色，其余格子为白色。

你将收到 $Q$ 个查询。对每个查询，请回答以下问题：

• 给定整数 $A,B,C,D$，求从上往下数第 $A$ 行到第 $B$ 行（含端点）、从左往右数第 $C$ 列到第 $D$ 列（含端点）所构成的矩形区域内包含的黑色格子数量。

The input is given from Standard Input in the following format:

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

Each query $\mathrm{query}_i ~ (1 \le i \le Q)$ is given in the form

$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$

Output $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

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

Sample 1 Explanation:

The black squares are located as shown in the figure above. The $1$-st query asks for the number of black squares within the blue rectangle at the upper left, the $2$-nd query within the red rectangle at the lower right, and the $3$-rd query within the green rectangle at the upper right.

Thus, output $4, 3, 0$, respectively.

Constraints

• $1 \le N,M,Q \le 2\times10^5$
• $1 \le L_i \le R_i \le M$
• For each query, $1 \le A \le B \le N$.
• For each query, $1 \le C \le D \le M$.
• All input values are integers.

样例 1 解释：

黑色方格的位置如上图所示。第 $1$ 个查询要求计算左上角蓝色矩形区域内的黑色方格数量，第 $2$ 个查询要求计算右下角红色矩形区域内的黑色方格数量，第 $3$ 个查询要求计算右上角绿色矩形区域内的黑色方格数量。

因此，依次输出 $4,\ 3,\ 0$。

限制条件

• $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$。
• 所有输入值均为整数。