火力覆盖

时间限制：$1s$

空间限制：$512MB$

输入文件：$cover.in$

输出文件：$cover.out$

题目背景

作为罗德岛的博士，你正在指挥干员进行作战……

题目描述

战场可以简化为一条 $[1,n]$ 的线段，敌人会随机地出现在战场上。一共有 $Q$ 波敌人，第 $i$ 波敌人会出现在 $[l_i,r_i]$ 之内的每一个位置。

您手下有 $m$ 位干员，第 $i$ 位干员的攻击覆盖范围为 $[x_i,y_i]$。作为博士，你需要恰当地指挥干员，消灭出现的敌人。您可以认为，只要敌人位于某一干员的攻击范围内，那么他一定会被消灭。

对于每一波敌人，您需要回答：最少多少干员出手，便可以全歼这一波敌人？

输入格式

第一行，三个整数，$n,m,Q$，含义如上。

接下来 $m$ 行，第 $i$ 行两个整数 $x_i,y_i$，表示第 $i$ 位干员的攻击覆盖范围。

接下来 $Q$ 行，第 $i$ 行两个整数 $l_i,r_i$，表示第 $i$ 波敌人的出现范围。

输出格式

$Q$ 行，第 $i$ 行一个整数 $ans_i$，表示消灭第 $i$ 波敌人最少需要 $ans_i$ 位干员出手。

样例组

输入样例

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

输出样例

3
2

提示说明

对于第 1 波敌人，让三位干员都出手；

对于第 2 波敌人，仅让第二、第三位干员出手即可。

注意！第 1 波敌人不能只用第一、第三位干员，因为这样的话区间 $[2,3]$ 是没有被覆盖到的。

数据范围

对于 40% 的数据，满足 $n,m,Q\leq5000$；

另有 20% 的数据，满足 $Q = 1$；

对于 100% 的数据，满足 $n,m,Q\leq10^6$。

P.S.我们保证，干员的攻击范围可以覆盖整个战场。