推荐温度统计

课堂重述版 · 差分与前缀和 · 来源：Codeforces 816B Karen and Coffee

题目描述

有 $n$ 份配方，每份配方推荐一个整数温度闭区间 $[l_i,r_i]$。若某个温度被至少 $k$ 份配方推荐，则称它为合适温度。有 $q$ 次询问，每次给出区间 $[a,b]$，求其中合适温度的个数。

输入格式

第一行三个整数 $n,k,q$。接下来 $n$ 行，每行两个整数 $l_i,r_i$。接下来 $q$ 行，每行两个整数 $a,b$。

输出格式

对每个询问输出一行，表示区间 $[a,b]$ 中合适温度的个数。

数据范围与约定

$1 \le k \le n \le 2\times 10^5$，$1 \le q \le 2\times 10^5$，所有温度和询问端点都在 $[1,2\times 10^5]$ 内。

样例输入

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

样例输出

2
2
4

样例说明

各温度被推荐的次数为 $1,2,2,3,2,1$（温度 $1$ 到 $6$）。合适温度为 $2,3,4,5$。区间 $[1,3]$ 中有 $2$ 个，$[4,5]$ 中有 $2$ 个，$[1,6]$ 中有 $4$ 个。

说明

课堂重述题，数据由 src/gen.py 重新生成，和原站评测数据不同。