Problem Statement

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.

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.

Input

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$

Output

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

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

4
3
0

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.

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

• Source: AtCoder ABC 477 F