完全包含的列车

题目描述

高桥王国有 $1$ 条东西走向的铁路。铁路沿线有 $N$ 个城市,从西到东依次编号为城市 $1, 2, 3, \cdots, N$。

一家名为 AtCoder Express 的公司拥有 $M$ 趟列车,列车 $i$ 行驶在城市 $L_i$ 到城市 $R_i$ 的区间(也可能有 $L_i = R_i$ 的情况)。

作为这个王国的国王,高桥君对 $Q$ 个问题产生了兴趣。具体来说,他想知道当 $i=1, 2, 3, \dots, Q$ 时,下面这个问题的答案:

• 行驶区间完全包含在城市 $p_i$ 到城市 $q_i$ 之间的列车数量。换句话说,就是满足 $p_i \leq L_j$ 且 $R_j \leq q_i$ 的列车 $j$ 的数量。

高桥君是天才。但即便是他,也无法处理海量的数据。请替高桥君求出这 $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$ 之间的列车数量。

样例

2 3 1
1 1
1 2
2 2
1 2

3

所有列车的行驶区间都包含在城市 $1$ 到城市 $2$ 之间,所以这个问题的答案是 $3$。

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

1
1

第 $1$ 个问题是关于城市 $1$ 到城市 $7$ 的区间。行驶区间完全包含在该区间内的列车只有列车 $1$。 第 $2$ 个问题是关于城市 $3$ 到城市 $10$ 的区间。行驶区间完全包含在该区间内的列车只有列车 $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

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