| Codeforces Round 419 (Div. 2) |
|---|
| Закончено |
Для того, чтобы оставаться бодрой и внимательной во время занятий, Карен нужен кофе!
Карен — поклонница кофе — хочет узнать оптимальную температуру заваривания кофе. Для этого она потратила некоторое время на чтение нескольких книг рецептов, в том числе общепризнанную книгу «Искусство ковфефе».
Карен знает n рецептов кофе. i-й из них рекомендует заваривать кофе при температуре от li до ri градусов включительно.
Карен считает, что температура является приемлемой, если хотя бы k рецептов рекомендуют ее.
Карен очень непостоянная, поэтому у нее есть q вопросов. В каждом вопросе она хочет заварить кофе с целочисленной температурой от a до b градусов включительно, и хочет узнать, сколько приемлемых целочисленных температур находятся в этом промежутке.
В первой строке содержится три целых числа n, k (1 ≤ k ≤ n ≤ 200000) и q (1 ≤ q ≤ 200000) — число рецептов, минимальное количество рецептов, необходимое для признания температуры приемлемой, и количество вопросов Карен, соответственно.
Следующие n строк описывают рецепты. А именно, i-я их этих строк содержит два целых числа li и ri (1 ≤ li ≤ ri ≤ 200000), означающих, что i-й рецепт рекомендует заваривать кофе с температурой между li и ri градусами включительно.
Следующие q строк описывают вопросы Карен. Каждая их этих строк содержит два целых числа a и b (1 ≤ a ≤ b ≤ 200000), означающих, что она хочет узнать число приемлемых целочисленных температур между 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
В первом примере Карен знает 3 рецепта.
- Первый рекомендует заваривать кофе при температуре между 91 и 94 градусами включительно.
- Второй рекомендует заваривать кофе при температуре между 92 и 97 градусами включительно.
- Третий рекомендует заваривать кофе при температуре между 97 и 99 градусами включительно.
Температура является приемлемой, если хотя бы 2 рецепта ее рекомендуют.
У Карен 4 вопроса.
В первом вопросе она хочет узнать число приемлемых целочисленных температур между 92 и 94 градусами включительно. Таких 3: 92, 93 и 94 градуса являются приемлемыми.
Во втором вопросе она хочет узнать число приемлемых целочисленных температур между 93 и 97 градусами включительно. Таких 3: 93, 94 и 97 градуса являются приемлемыми.
В третьем вопросе она хочет узнать число приемлемых целочисленных температур между и 95 и 96 градусами включительно. Таких нет.
В последнем вопросе она хочет узнать число приемлемых целочисленных температур между 90 and 100 градусами включительно. Таких 4: 92, 93, 94 и 97 градуса являются приемлемыми.
Во втором примере Карен знает 2 рецепта.
- Первых их них, «wikiHow to make Cold Brew Coffee», рекомендует заваривать кофе при температуре ровно 1 градус.
- Второй, «Разве является кофе то, что не заварено при температуре не меньше 36.3306 температур Солнца?», рекомендует заваривать кофе при ровно 200000 градусов.
Температура является приемлемой, если хотя бы 1 рецепт ее рекомендует.
В первом и единственном вопросе Карен хочет узнать, сколько приемлемых температур действительно являются осмысленными. Таких нет.
