CF816B Karen and Coffee

为了在上课时保持清醒和专注，Karen 需要喝点咖啡！ Karen 是一位咖啡爱好者，她想知道冲泡完美咖啡的最佳温度。实际上，她花了一些时间阅读了几本食谱，包括备受赞誉的《The Art of the Covfefe》。 她一共掌握了 $n$ 种咖啡配方。第 $i$ 个配方建议咖啡应在 $l_i$ 到 $r_i$ 度（包含端点）之间冲泡，以获得最佳口感。 Karen 认为，如果有至少 $k$ 个配方推荐某个温度，则该温度为可接受温度。 Karen 的想法总是变化多端，于是她总共提出了 $q$ 个问题。每个问题，她都会给定一个温度范围 $a$ 到 $b$，想让你告诉她，在这个范围内有多少个可接受的整数温度。

输入的第一行包含三个整数 $n,\ k$（$1 \leq k \leq n \leq 200000$）、$q$（$1 \leq q \leq 200000$），分别表示配方数量、某个温度被判定为可接受所需的最少配方数，以及 Karen 提出的查询个数。 接下来的 $n$ 行描述每个配方。具体地，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq 200000$），表示第 $i$ 个配方推荐咖啡应在 $l_i$ 到 $r_i$ 度（包含端点）之间冲泡。 接下来的 $q$ 行描述各个问题。每行包含两个整数 $a$ 和 $b$（$1 \leq a \leq b \leq 200000$），表示她想知道在 $a$ 到 $b$（包含端点）度之间有多少个可接受的整数温度。

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

在第一个测试点中，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. 第一个配方建议只在 $1$ 度冲泡咖啡。 2. 第二个配方建议只在 $200000$ 度冲泡咖啡。 只要某个温度区间内至少有 $1$ 个配方推荐，则该温度为可接受温度。 她有且仅有一个问题，询问在合理范围内有多少可接受整数温度。实际上没有。 由 ChatGPT 5 翻译