#sjjx07. Karen and Coffee

Karen and Coffee

题目描述

为了在上课时保持清醒和专注,Karen 需要喝点咖啡!

img

Karen 是一位咖啡爱好者,她想知道冲泡完美咖啡的最佳温度。实际上,她花了一些时间阅读了几本食谱,包括备受赞誉的《The Art of the Covfefe》。

她一共掌握了 nn 种咖啡配方。第 ii 个配方建议咖啡应在 lil_i 到 rir_i 度(包含端点)之间冲泡,以获得最佳口感。

Karen 认为,如果有至少 kk 个配方推荐某个温度,则该温度为可接受温度。

Karen 的想法总是变化多端,于是她总共提出了 qq 个问题。每个问题,她都会给定一个温度范围 aa 到 bb,想让你告诉她,在这个范围内有多少个可接受的整数温度。

输入格式

输入的第一行包含三个整数 n, kn,\ k(1≤k≤n≤2000001 \leq k \leq n \leq 200000)、qq(1≤q≤2000001 \leq q \leq 200000),分别表示配方数量、某个温度被判定为可接受所需的最少配方数,以及 Karen 提出的查询个数。

接下来的 nn 行描述每个配方。具体地,第 ii 行包含两个整数 lil_i 和 rir_i(1≤li≤ri≤2000001 \leq l_i \leq r_i \leq 200000),表示第 ii 个配方推荐咖啡应在 lil_i 到 rir_i 度(包含端点)之间冲泡。

接下来的 qq 行描述各个问题。每行包含两个整数 aa 和 bb(1≤a≤b≤2000001 \leq a \leq b \leq 200000),表示她想知道在 aa 到 bb(包含端点)度之间有多少个可接受的整数温度。

输出格式

对于每一个问题,输出一行一个整数,表示在 aa 到 bb 度之间有多少个可接受的整数温度。

输入输出样例 #1

输入 #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

2 1 1
1 1
200000 200000
90 100

输出 #2

0

说明/提示

在第一个测试点中,Karen 掌握了 33 个配方。

  1. 第一个推荐温度区间为 9191 到 9494 度(包含端点)。
  2. 第二个推荐温度区间为 9292 到 9797 度(包含端点)。
  3. 第三个推荐温度区间为 9797 到 9999 度(包含端点)。

只要某个温度区间内至少有 22 个配方推荐,则该温度为可接受温度。

她一共提出了 44 个问题。

在第一个询问中,她想知道在 9292 到 9494 度之间的可接受整数温度有多少。答案是 33,因为 92, 93, 9492,\ 93,\ 94 度都是可接受的。

在第二个询问中,她想知道在 9393 到 9797 度之间的可接受整数温度有多少。答案是 33,因为 93, 94, 9793,\ 94,\ 97 度都是可接受的。

在第三个询问中,她想知道在 9595 到 9696 度之间的可接受整数温度有多少。没有可接受的温度。

在最后一个询问中,她想知道在 9090 到 100100 度之间有多少个可接受的整数温度。答案是 44,分别是 92, 93,94,9792,\ 93, 94, 97 度。

在第二个测试点中,Karen 掌握了 22 个配方。

  1. 第一个配方建议只在 11 度冲泡咖啡。
  2. 第二个配方建议只在 200000200000 度冲泡咖啡。

只要某个温度区间内至少有 11 个配方推荐,则该温度为可接受温度。

她有且仅有一个问题,询问在合理范围内有多少可接受整数温度。实际上没有。