1824: Продаж квитків
Перегляд у форматі PDFУ нових елітних електричках кожному пасажиру відведено сидяче місце. Звичайно, кількість сидячих місць обмежена і на всіх їх може не вистачити.
Маршрут електрички проходить через ~N+1~ станцію. Станції пронумеровані від 0 до ~N~. Коли людина хоче купити квиток, він називає два числа ~x~ та ~y~ – номери станцій, звідки і куди він хоче їхати. За наявності хоча б одного місця сидіння на цій ділянці на момент покупки йому продається квиток, інакше видається повідомлення «квитків немає» і квиток не продається.
Ваше завдання – написати програму, яка обслуговує такі запити в порядку їх приходу.
Формат вхідних даних
У першому рядку містяться три числа ~N~ – кількість станцій (~1 ≤ N ≤ 200 000~), ~K~ – кількість місць в електричці (~1 ≤ K ≤ 1000~) та ~M~ – кількість запитів (~1 ≤ M ≤ 100 000)~.
У наступних ~M~ рядках описані запити, кожен із яких складається з двох чисел ~x~ та ~y~ (~0 ≤ x < y \le N~).
Формат вихідних даних
На кожен запит ваша програма повинна видавати результат у вигляді числа 0, якщо квиток не продається і 1, якщо квиток був проданий. Кожен результат має бути на окремому рядку
Оцінювання
- 30%, ~N,M \le 10000~, тести 1-8
- 70%, без додаткових обмежень, тести 9-17
Приклад вхідних даних
5 2 4
0 4
1 2
1 4
2 4
Приклад вихідних даних
1
1
0
1
Коментарі
запити будуть дані в порядку зростання чи в довільному?
в довільному