Для того, чтобы оставаться бодрой и внимательной во время занятий, Карен нужен кофе!
Карен — поклонница кофе — хочет узнать оптимальную температуру заваривания кофе. Для этого она потратила некоторое время на чтение нескольких книг рецептов, в том числе общепризнанную книгу «Искусство ковфефе».
Карен знает n рецептов кофе. i-й из них рекомендует заваривать кофе при температуре от li до ri градусов включительно.
Карен считает, что температура является приемлемой, если хотя бы k рецептов рекомендуют ее.
Карен очень непостоянная, поэтому у нее есть q вопросов. В каждом вопросе она хочет заварить кофе с целочисленной температурой от a до b градусов включительно, и хочет узнать, сколько приемлемых целочисленных температур находятся в этом промежутке.
Выходные данные
Для каждого вопроса выведите одно целое число — число приемлемых целочисленных температур между a и b градусами включительно.
Примечание
В первом примере Карен знает 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 рецепт ее рекомендует.
В первом и единственном вопросе Карен хочет узнать, сколько приемлемых температур действительно являются осмысленными. Таких нет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2 4
91 94
92 97
97 99
92 94
93 97
95 96
90 100
|
3
3
0
4
|
|
2
|
2 1 1
1 1
200000 200000
90 100
|
0
|