Рецепты кофе

У Карен $n$ рецептов кофе: $i$-й рецепт советует варить кофе при температуре от $l_i$ до $r_i$ градусов (обе границы включительно). Целая температура называется допустимой, если её советуют хотя бы $k$ рецептов.

Карен задаёт $q$ вопросов: сколько допустимых целых температур от $a$ до $b$ градусов (включительно)?

В первой строке $n$, $k$, $q$ ($1 \le k \le n \le 2 \cdot 10^5$, $1 \le q \le 2 \cdot 10^5$). В следующих $n$ строках $l_i$ и $r_i$, затем $q$ строк с $a$ и $b$ ($1 \le l_i \le r_i \le 200000$, $1 \le a \le b \le 200000$).

Для каждого вопроса одно число в отдельной строке.

Префиксы в два этапа. Разностный массив: для каждого рецепта $d_{l_i} \mathrel{+}= 1$, $d_{r_i + 1} \mathrel{-}= 1$; префиксные суммы $d$ дают число рецептов для каждой температуры. Затем $g_t = 1$, если это число $\ge k$, и по префиксным суммам $g$ каждый вопрос — $O(1)$.

В первом примере допустимы температуры $92, 93, 94, 97$.

Источник: Codeforces, задача 816B.