题目描述

In Takahashi Kingdom, there is a east-west railroad and $N$ cities along it, numbered $1$, $2$, $3$, ..., $N$ from west to east. A company called AtCoder Express possesses $M$ trains, and the train $i$ runs from City $L_i$ to City $R_i$ (it is possible that $L_i = R_i$). Takahashi the king is interested in the following $Q$ matters:

• The number of the trains that runs strictly within the section from City $p_i$ to City $q_i$, that is, the number of trains $j$ such that $p_i \leq L_j$ and $R_j \leq q_i$.

Although he is genius, this is too much data to process by himself. Find the answer for each of these $Q$ queries to help him.

在高桥王国，有一条东西走向的铁路，铁路沿线有 $N$ 个城市，从西向东依次编号为 $1$ 、 $2$ 、 $3$ ......、 $N$ 。一家名为_AtCoder Express_的公司拥有 $M$ 列火车， $i$ 列火车从 $L_i$ 市开往 $R_i$ 市（有可能是 $L_i = R_i$ ）。高桥国王对以下 $Q$ 事项感兴趣：

• 从城市 $p_i$ 到城市 $q_i$ 的区间内**严格运行的列车数，即 $j$ 中 $p_i \leq L_j$ 和 $R_j \leq q_i$ 的列车数。

虽然他是个天才，但这些数据太多，他一个人根本无法处理。请找出每个 $Q$ 查询的答案来帮助他。

输入格式

输入内容按以下格式标准输入：

$N$ $M$ $Q$
$L_1$ $R_1$
$L_2$ $R_2$
$:$
$L_M$ $R_M$
$p_1$ $q_1$
$p_2$ $q_2$
$:$
$p_Q$ $q_Q$

输出格式

打印 $Q$ 行。 $i$ -行应包含从城市 $p_i$ 到城市 $q_i$ 区间内**严格运行的列车编号。

样例 #1

样例输入 #1

2 3 1
1 1
1 2
2 2
1 2

样例输出 #1

3

样例 #2

样例输入 #2

10 3 2
1 5
2 8
7 10
1 7
3 10

样例输出 #2

1
1

样例 #3

样例输入 #3

10 10 10
1 6
2 9
4 5
4 7
4 7
5 8
6 6
6 7
7 9
10 10
1 8
1 9
1 10
2 8
2 9
2 10
3 8
3 9
3 10
1 10

样例输出 #3

7
9
10
6
8
9
6
7
8
10

说明

数据规模与约定

• $N$ 是介于 $1$ 和 $500$ （含）之间的整数。
• $M$ 是介于 $1$ 和 $200 \ 000$ （含）之间的整数。
• $Q$ 是介于 $1$ 和 $100 \ 000$ （含）之间的整数。
• $1 \leq L_i \leq R_i \leq N$ $(1 \leq i \leq M)$
• $1 \leq p_i \leq q_i \leq N$ $(1 \leq i \leq Q)$

样例 $1$ 解释

由于所有列车都在城市 $1$ 至城市 $2$ 区间内运行，因此唯一查询的答案为 $3$ 。

样例 $2$ 解释

第一个查询是从城市 $1$ 到 $7$ 的区间。在该区间内只有一趟列车严格运行：列车 $1$ 。第二个查询是从城市 $3$ 到 $10$ 的区段。在该区段内只有一趟列车严格运行：列车 $3$ 。