Coffee recipes

Karen has $n$ coffee recipes: recipe $i$ recommends brewing at a temperature from $l_i$ to $r_i$ degrees (both inclusive). An integer temperature is admissible if at least $k$ recipes recommend it.

Karen asks $q$ questions: how many admissible integer temperatures are there from $a$ to $b$ degrees (inclusive)?

The first line contains $n$, $k$, $q$ ($1 \le k \le n \le 2 \cdot 10^5$, $1 \le q \le 2 \cdot 10^5$). The next $n$ lines contain $l_i$ and $r_i$, then $q$ lines contain $a$ and $b$ ($1 \le l_i \le r_i \le 200000$, $1 \le a \le b \le 200000$).

For every question print one number on a separate line.

Prefix sums in two stages. Difference array: for every recipe $d_{l_i} \mathrel{+}= 1$, $d_{r_i + 1} \mathrel{-}= 1$; the prefix sums of $d$ give the number of recipes for every temperature. Then $g_t = 1$ if that number is $\ge k$, and with prefix sums of $g$ every question is $O(1)$.

In the first example the admissible temperatures are $92, 93, 94, 97$.

Source: Codeforces, problem 816B.