{"raw_statement":[{"iden":"statement","content":"To stay woke and attentive during classes, Karen needs some coffee!\n\n<center>![image](https://espresso.codeforces.com/d3ec9da91288120e5f9bf542a33dfb52f6abc639.png)</center>Karen, a coffee aficionado, wants to know the optimal temperature for brewing the perfect cup of coffee. Indeed, she has spent some time reading several recipe books, including the universally acclaimed \"The Art of the Covfefe\".\n\nShe knows _n_ coffee recipes. The _i_\\-th recipe suggests that coffee should be brewed between _l__i_ and _r__i_ degrees, inclusive, to achieve the optimal taste.\n\nKaren thinks that a temperature is _admissible_ if at least _k_ recipes recommend it.\n\nKaren has a rather fickle mind, and so she asks _q_ questions. In each question, given that she only wants to prepare coffee with a temperature between _a_ and _b_, inclusive, can you tell her how many admissible integer temperatures fall within the range?"},{"iden":"input","content":"The first line of input contains three integers, _n_, _k_ (1 ≤ _k_ ≤ _n_ ≤ 200000), and _q_ (1 ≤ _q_ ≤ 200000), the number of recipes, the minimum number of recipes a certain temperature must be recommended by to be admissible, and the number of questions Karen has, respectively.\n\nThe next _n_ lines describe the recipes. Specifically, the _i_\\-th line among these contains two integers _l__i_ and _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ 200000), describing that the _i_\\-th recipe suggests that the coffee be brewed between _l__i_ and _r__i_ degrees, inclusive.\n\nThe next _q_ lines describe the questions. Each of these lines contains _a_ and _b_, (1 ≤ _a_ ≤ _b_ ≤ 200000), describing that she wants to know the number of admissible integer temperatures between _a_ and _b_ degrees, inclusive."},{"iden":"output","content":"For each question, output a single integer on a line by itself, the number of admissible integer temperatures between _a_ and _b_ degrees, inclusive."},{"iden":"examples","content":"Input\n\n3 2 4\n91 94\n92 97\n97 99\n92 94\n93 97\n95 96\n90 100\n\nOutput\n\n3\n3\n0\n4\n\nInput\n\n2 1 1\n1 1\n200000 200000\n90 100\n\nOutput\n\n0"},{"iden":"note","content":"In the first test case, Karen knows 3 recipes.\n\n1.  The first one recommends brewing the coffee between 91 and 94 degrees, inclusive.\n2.  The second one recommends brewing the coffee between 92 and 97 degrees, inclusive.\n3.  The third one recommends brewing the coffee between 97 and 99 degrees, inclusive.\n\nA temperature is _admissible_ if at least 2 recipes recommend it.\n\nShe asks 4 questions.\n\nIn her first question, she wants to know the number of admissible integer temperatures between 92 and 94 degrees, inclusive. There are 3: 92, 93 and 94 degrees are all admissible.\n\nIn her second question, she wants to know the number of admissible integer temperatures between 93 and 97 degrees, inclusive. There are 3: 93, 94 and 97 degrees are all admissible.\n\nIn her third question, she wants to know the number of admissible integer temperatures between 95 and 96 degrees, inclusive. There are none.\n\nIn her final question, she wants to know the number of admissible integer temperatures between 90 and 100 degrees, inclusive. There are 4: 92, 93, 94 and 97 degrees are all admissible.\n\nIn the second test case, Karen knows 2 recipes.\n\n1.  The first one, \"wikiHow to make Cold Brew Coffee\", recommends brewing the coffee at exactly 1 degree.\n2.  The second one, \"What good is coffee that isn't brewed at at least 36.3306 times the temperature of the surface of the sun?\", recommends brewing the coffee at exactly 200000 degrees.\n\nA temperature is _admissible_ if at least 1 recipe recommends it.\n\nIn her first and only question, she wants to know the number of admissible integer temperatures that are actually reasonable. There are none."}],"translated_statement":[{"iden":"statement","content":"为了在课堂上保持清醒和专注，Karen 需要一些咖啡！\n\nKaren 是一位咖啡爱好者，她想知道冲泡完美一杯咖啡的最佳温度。事实上，她花了一些时间阅读了几本食谱书籍，包括广受赞誉的《The Art of the Covfefe》。\n\n她知道 #cf_span[n] 种咖啡配方。第 #cf_span[i] 种配方建议，咖啡应在 #cf_span[li] 到 #cf_span[ri] 摄氏度之间（含端点）冲泡，以达到最佳口感。\n\nKaren 认为，如果至少有 #cf_span[k] 种配方推荐某个温度，则该温度是 _可接受的_。\n\nKaren 的想法相当多变，因此她提出了 #cf_span[q] 个问题。在每个问题中，给定她只想在 #cf_span[a] 到 #cf_span[b] 摄氏度之间（含端点）冲泡咖啡，你能告诉她有多少个可接受的整数温度落在该范围内吗？\n\n输入的第一行包含三个整数：#cf_span[n]、#cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 200000]）和 #cf_span[q]（#cf_span[1 ≤ q ≤ 200000]），分别表示配方数量、一个温度要被认定为可接受所需的最少推荐配方数，以及 Karen 提出的问题数量。\n\n接下来的 #cf_span[n] 行描述了配方。具体来说，这些行中的第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ 200000]），表示第 #cf_span[i] 种配方建议咖啡应在 #cf_span[li] 到 #cf_span[ri] 摄氏度之间（含端点）冲泡。\n\n接下来的 #cf_span[q] 行描述了问题。每行包含 #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ a ≤ b ≤ 200000]），表示她想知道在 #cf_span[a] 到 #cf_span[b] 摄氏度之间（含端点）有多少个可接受的整数温度。\n\n对于每个问题，请在单独的一行上输出一个整数，表示在 #cf_span[a] 到 #cf_span[b] 摄氏度之间（含端点）的可接受整数温度数量。\n\n在第一个测试用例中，Karen 知道 #cf_span[3] 种配方。\n\n一个温度是 _可接受的_，当且仅当至少有 #cf_span[2] 种配方推荐它。\n\n她提出了 #cf_span[4] 个问题。\n\n在她的第一个问题中，她想知道在 #cf_span[92] 到 #cf_span[94] 摄氏度之间（含端点）有多少个可接受的整数温度。共有 #cf_span[3] 个：#cf_span[92]、#cf_span[93] 和 #cf_span[94] 摄氏度都是可接受的。\n\n在她的第二个问题中，她想知道在 #cf_span[93] 到 #cf_span[97] 摄氏度之间（含端点）有多少个可接受的整数温度。共有 #cf_span[3] 个：#cf_span[93]、#cf_span[94] 和 #cf_span[97] 摄氏度都是可接受的。\n\n在她的第三个问题中，她想知道在 #cf_span[95] 到 #cf_span[96] 摄氏度之间（含端点）有多少个可接受的整数温度。没有。\n\n在她的最后一个问题中，她想知道在 #cf_span[90] 到 #cf_span[100] 摄氏度之间（含端点）有多少个可接受的整数温度。共有 #cf_span[4] 个：#cf_span[92]、#cf_span[93]、#cf_span[94] 和 #cf_span[97] 摄氏度都是可接受的。\n\n在第二个测试用例中，Karen 知道 #cf_span[2] 种配方。\n\n一个温度是 _可接受的_，当且仅当至少有 #cf_span[1] 种配方推荐它。\n\n在她的第一个也是唯一一个问题中，她想知道有多少个可接受的整数温度是实际合理的。没有。"},{"iden":"input","content":"输入的第一行包含三个整数：#cf_span[n]、#cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 200000]）和 #cf_span[q]（#cf_span[1 ≤ q ≤ 200000]），分别表示配方数量、一个温度要被认定为可接受所需的最少推荐配方数，以及 Karen 提出的问题数量。接下来的 #cf_span[n] 行描述了配方。具体来说，这些行中的第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ 200000]），表示第 #cf_span[i] 种配方建议咖啡应在 #cf_span[li] 到 #cf_span[ri] 摄氏度之间（含端点）冲泡。接下来的 #cf_span[q] 行描述了问题。每行包含 #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ a ≤ b ≤ 200000]），表示她想知道在 #cf_span[a] 到 #cf_span[b] 摄氏度之间（含端点）有多少个可接受的整数温度。"},{"iden":"output","content":"对于每个问题，请在单独的一行上输出一个整数，表示在 #cf_span[a] 到 #cf_span[b] 摄氏度之间（含端点）的可接受整数温度数量。"},{"iden":"examples","content":"输入3 2 491 9492 9797 9992 9493 9795 9690 100输出3304输入2 1 11 1200000 20000090 100输出0"},{"iden":"note","content":"在第一个测试用例中，Karen 知道 #cf_span[3] 种配方。第一种配方建议在 #cf_span[91] 到 #cf_span[94] 摄氏度之间（含端点）冲泡咖啡。第二种配方建议在 #cf_span[92] 到 #cf_span[97] 摄氏度之间（含端点）冲泡咖啡。第三种配方建议在 #cf_span[97] 到 #cf_span[99] 摄氏度之间（含端点）冲泡咖啡。一个温度是 _可接受的_，当且仅当至少有 #cf_span[2] 种配方推荐它。她提出了 #cf_span[4] 个问题。在她的第一个问题中，她想知道在 #cf_span[92] 到 #cf_span[94] 摄氏度之间（含端点）有多少个可接受的整数温度。共有 #cf_span[3] 个：#cf_span[92]、#cf_span[93] 和 #cf_span[94] 摄氏度都是可接受的。在她的第二个问题中，她想知道在 #cf_span[93] 到 #cf_span[97] 摄氏度之间（含端点）有多少个可接受的整数温度。共有 #cf_span[3] 个：#cf_span[93]、#cf_span[94] 和 #cf_span[97] 摄氏度都是可接受的。在她的第三个问题中，她想知道在 #cf_span[95] 到 #cf_span[96] 摄氏度之间（含端点）有多少个可接受的整数温度。没有。在她的最后一个问题中，她想知道在 #cf_span[90] 到 #cf_span[100] 摄氏度之间（含端点）有多少个可接受的整数温度。共有 #cf_span[4] 个：#cf_span[92]、#cf_span[93]、#cf_span[94] 和 #cf_span[97] 摄氏度都是可接受的。在第二个测试用例中，Karen 知道 #cf_span[2] 种配方。第一种配方，“wikiHow 制作冷萃咖啡”，建议在恰好 #cf_span[1] 摄氏度冲泡咖啡。第二种配方，“如果咖啡不是在至少 #cf_span[36.3306] 倍太阳表面温度下冲泡，那有什么意义？”，建议在恰好 #cf_span[200000] 摄氏度冲泡咖啡。一个温度是 _可接受的_，当且仅当至少有 #cf_span[1] 种配方推荐它。在她的第一个也是唯一一个问题中，她想知道有多少个可接受的整数温度是实际合理的。没有。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k, q \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 200000 $ and $ 1 \\leq q \\leq 200000 $.  \nLet $ R = \\{(l_i, r_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be a set of $ n $ intervals, where each $ l_i, r_i \\in \\mathbb{Z} $ and $ 1 \\leq l_i \\leq r_i \\leq 200000 $.  \nLet $ T = \\{ t \\in \\mathbb{Z} \\mid 1 \\leq t \\leq 200000 \\} $ be the set of all possible integer temperatures.  \n\nFor each $ t \\in T $, define the coverage count:  \n$$ c(t) = \\left| \\left\\{ i \\in \\{1, \\dots, n\\} \\mid t \\in [l_i, r_i] \\right\\} \\right| $$  \n\nA temperature $ t \\in T $ is **admissible** if and only if $ c(t) \\geq k $.  \n\nLet $ A = \\{ t \\in T \\mid c(t) \\geq k \\} $ be the set of admissible temperatures.  \n\n**Constraints**  \n1. $ 1 \\leq k \\leq n \\leq 200000 $  \n2. $ 1 \\leq l_i \\leq r_i \\leq 200000 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq a_j \\leq b_j \\leq 200000 $ for each query $ j \\in \\{1, \\dots, q\\} $  \n\n**Objective**  \nFor each query $ j \\in \\{1, \\dots, q\\} $, compute:  \n$$  \n\\left| A \\cap [a_j, b_j] \\right|  \n$$  \nwhere $ [a_j, b_j] = \\{ t \\in \\mathbb{Z} \\mid a_j \\leq t \\leq b_j \\} $.","simple_statement":null,"has_page_source":false}