У нових елітних електричках кожному пасажиру відведено сидяче місце. Звичайно, кількість сидячих місць обмежена і на всіх їх може не вистачити.

Маршрут електрички проходить через \(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 <= N\)).

Формат вихідних даних

На кожен запит ваша програма повинна видавати результат у вигляді числа 0, якщо квиток не продається і 1, якщо квиток був проданий. Кожен результат має бути на окремому рядку

Приклад вхідних даних

5 2 4
0 4
1 2
1 4
2 4

Приклад вихідних даних

1
1
0
1