题目描述

在高桥王国，有一条东西方向的铁路，沿线有 $N$ 个城市，从西到东编号为 $1、2...、N$。 公司名为 AtCoder Express 拥有 $M$ 列火车，第 $i$ 列火车从第 $L_i$ 号城市到第 $R_i$ 号城市运行（可能有 $L_i=R_i$）。 高桥王对以下 $Q$ 个问题感兴趣：

• 运行 完全区间 在从第 $p_i$ 号城市到第 $q_i$ 号城市的火车数，即满足 $p_i≤L_j$ 且$R_j \leq q_i$ 的 $j$ 的个数。

虽然高桥王很聪明，但这个数据量对他来说太庞大了。 帮助他回答这 $Q$ 个问题。

输入

在标准输入中以下面的格式给出输入：

$N\ M\ Q$

$L_1R_1$

$L_2R_2$

...

$L_MR_M$

$p_1q_1$

$p_2q_2$

...

$p_Qq_Q$

输出

输出 $Q$ 行。 第 $i$ 行应该包含运行 完全区间 在从第 $p_i$ 号城市到第 $q_i$ 号城市的火车数。

2 3 1
1 1
1 2
2 2
1 2

3

【样例1解释】 由于所有火车都运行在从第 1 号城市到第 2 号城市的区间内，唯一的查询的答案是 3。

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

1
1

【样例2解释】 第一个查询是在从第 1 号城市到第 7 号城市的区间内。在此区间内只有一列火车完全运行：火车 1。 第二个查询是在从第 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 和 200000 之间的整数（包含边界值）。
• $Q$ 是一个介于 1 和 100000 之间的整数（包含边界值）。
• $1≤p_i≤q_i≤N（1≤i≤M)$
• $1≤L_i≤R_i≤N(1≤i≤Q)$