为了在课堂上保持清醒和专心,凯伦需要一些咖啡!
咖啡爱好者凯伦想知道冲泡一杯完美咖啡的最佳温度。事实上,她花了一些时间阅读了几本食谱书籍,包括广受好评的《The Art of the Covfefe》。
她知道 n 个咖啡食谱。第 i 个配方建议咖啡应该在 li 和 ri 度(含)之间冲泡,以获得最佳口味。
Karen 认为,如果至少有 k 个食谱推荐某个温度,则该温度是可接受的。
凯伦的头脑相当善变,所以她问了q个问题。在每个问题中,假设她只想准备温度介于 a 和 b 之间(含)的咖啡,您能否告诉她有多少个允许的整数温度落在该范围内?
输入
输入的第一行包含三个整数,n、k (1 ≤ k ≤ n ≤ 200000) 和 q (1 ≤ q ≤ 200000)、食谱数量、一定温度下必须推荐的最少食谱数量以及 Karen 的问题数量。
接下来的 n 行描述了食谱。具体来说,其中的第 i 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ 200000),描述第 i 个配方建议在 li 和 ri 度之间(包括 li 和 ri 度)冲泡咖啡。
接下来的 q 行描述了问题。这些行中的每一行都包含 a 和 b,(1 ≤ a ≤ b ≤ 200000),描述她想知道 a 和 b 度(含)之间的允许整数温度的数量。
输出
对于每个问题,在一行中单独输出一个整数,即 a 度和 b 度(含)之间允许的整数温度的数量。
示例
输入 #1
3 2 4 91 94 92 97 97 99 92 94 93 97 95 96 90 100
输出 #1
3 3 0 4
输入 #2
2 1 1 1 1 200000 200000 90 100
输出 #2
0
注意
在第一个测试用例中,Karen 知道 3 个食谱。
1. 第一个建议在 91 至 94 度(含)之间冲泡咖啡。
2. 第二个建议在 92 至 97 度(含)之间冲泡咖啡。
3. 第三个建议在 97 度到 99 度(含)之间冲泡咖啡。
如果至少有 2 个食谱推荐某个温度,则该温度是可接受的。
她问了 4 个问题。
在第一个问题中,她想知道 92 到 94 度(含)之间允许的整数温度的数量。有3种:92度、93度、94度都可以。
在第二个问题中,她想知道 93 到 97 度(含)之间允许的整数温度的数量。有3种:93度、94度、97度都可以。
在第三个问题中,她想知道 95 到 96 度(含)之间允许的整数温度的数量。没有。
在她的最后一个问题中,她想知道 90 到 100 度(含)之间允许的整数温度的数量。有4种:92度、93度、94度、97度都可以。
在第二个测试用例中,Karen 知道 2 个食谱。
1. 第一个,“wikiHow to make Cold Brew Coffee”,建议在正好 1 度的温度下冲泡咖啡。
2. 第二个,“咖啡不是在太阳表面温度至少 36.3306 倍的温度下冲泡的,有什么好处?”,建议在 200000 度的温度下冲泡咖啡。
如果至少有 1 个配方推荐某个温度,则该温度是可接受的。
在她的第一个问题也是唯一的问题中,她想知道实际上合理的允许整数温度的数量。没有。