给定 n 个整数区间,其中第 i 个区间为 [li,ri] 。
n
i
[li,ri]
如果一个整数被至少 k 个给定区间所包含,就称这个整数为合格数。
k
你需要回答 q 个问题。
q
第 i 个问题给定两个整数 a,b ,请你计算 [a,b] 范围内有多少个合格数。
a,b
[a,b]
第一行包含三个整数 n,k,q 。
n,k,q
接下来 n 行,每行包含两个整数 li,ri ,表示一个给定区间。
li,ri
接下来 q 行,每行包含两个整数 a,b ,用来描述一个问题。
每个问题输出一行结果,一个整数,表示 [a,b] 范围内合格数的数量。
输入样例1:
3 2 4 1 4 2 7 7 9 2 4 3 7 5 6 1 10
输出样例1:
3 3 0 4
输入样例2:
2 1 1 1 1 100 100 9 10
输出样例2:
0
前 4 个测试点满足 1≤k≤n≤5 ,1≤q≤5 , 。
所有测试点满足 1≤k≤n≤2×10^5 ,1≤q≤2×10^5 ,1≤li≤ri≤2×10^5 ,1≤a≤b≤2×10^5 , , , 。