题目描述

有 $n$ 份冲泡建议。第 $i$ 份建议认为，温度在闭区间 $[l_i,r_i]$ 内都适合使用。

如果一个整数温度至少被 $k$ 份建议覆盖，就称它是合格温度。

接下来有 $q$ 次询问，每次给出一个温度区间 $[a,b]$，请回答这个区间中有多少个整数温度是合格温度。

输入格式

第一行输入三个整数 $n,k,q$。

接下来 $n$ 行，每行输入两个整数 $l_i,r_i$，表示一份建议覆盖的温度区间。

接下来 $q$ 行，每行输入两个整数 $a,b$，表示一次询问。

输出格式

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

样例

3 2 4
91 94
92 97
97 99
92 94
93 97
95 96
90 100

3
3
0
4

2 1 1
1 1
200000 200000
90 100

0

样例说明

样例 1 解释

已知 $n=3$，$k=2$，即一个整数温度至少被 2 份 建议覆盖才算合格。

三份建议覆盖的温度区间为：

1. $[91, 94]$
2. $[92, 97]$
3. $[97, 99]$

统计每个整数温度被多少份建议覆盖：

因此，合格温度为：92, 93, 94, 97。

接下来回答 4 次询问：

1. 询问 $[92, 94]$：合格温度有 92、93、94，共 3 个。
2. 询问 $[93, 97]$：合格温度有 93、94、97，共 3 个。
3. 询问 $[95, 96]$：合格温度有 0 个，输出 0。
4. 询问 $[90, 100]$：合格温度有 92、93、94、97，共 4 个。

与样例输出一致。

数据范围

• 对于 $30\%$ 的数据，$n,q\le 1000$。
• 对于 $100\%$ 的数据，$1\le k\le n\le 200000$，$1\le q\le 200000$，$1\le l_i\le r_i\le 200000$，$1\le a\le b\le 200000$。