G. Билеты на МЦД

Маршрут электрички проходит через $N + 1$ станцию, занумерованных от 0 до $N$; в электричке $K$ сидячих мест. Пассажир называет станции $x$ и $y$ - откуда и куда едет. Билет продаётся, если на всём участке от $x$ до $y$ есть хотя бы одно свободное место.

Обрабатывайте запросы в порядке поступления.

В первой строке - числа $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, если билет продан, и 0 иначе. Каждый ответ в отдельной строке.