G. Где не хватило места

Та же электричка, что в классной задаче G, но при отказе нужно назвать первую станцию, начиная с которой мест уже нет.

Раньше хватало максимума на отрезке: если он меньше $K$, билет продаётся. Теперь нужен ещё и поиск первой позиции, где загрузка достигла $K$.

В первой строке - числа $N$ ($1 \le N \le 2 \cdot 10^5$), $K$ ($1 \le K \le 1000$) и $M$ ($1 \le M \le 10^5$).

В следующих $M$ строках - запросы: пары $x$ и $y$ ($0 \le x < y \le N$).

На каждый запрос выведите $-1$, если билет продан, и номер первой станции, начиная с которой не хватило места, иначе.

Станция считается перегруженной, если на перегоне от неё до следующей станции уже занято $K$ мест.