Вы занимаетесь разработкой системы по продаже билетов на поезда. Несмотря на то, что поезда ходят по множеству различных маршрутов, вы будете работать только с одним из них. Маршрут рассматриваемого поезда состоит из n остановок: маршрут начинается в первой из них, а заканчивается в n-й, соответственно. Всего в поезде имеется m мест для пассажиров.
Эта система будет использоваться для продажи билетов пассажирам. При покупке билета пассажир указывает номер станции L, на которой он хочет сесть на поезд и номер станции R, на которой он хочет сойти с поезда. Если у одного пассажира есть билет до станции S, а другой хочет купить билет от станции S, то они друг другу не мешают: второй может занимать только что освободившееся место первого. Система должна сообщить пассажиру следующую информацию:
- f, где f число свободных мест мест между L-й и R-й станциями, если хотя бы одно такое место есть. В этом случае пассажир покупает один билет с L-й по R-ю станцию.
- 0 если подходящих свободных мест нет. В этом случае пассажир билет не покупает.
Входные данные
В первой находятся натуральные числа n (2 ≤ n ≤ 100), m (1 ≤ m ≤ 100) и k (1 ≤ k ≤ 100) — число станций в маршруте поезда, максимальное число пассажиров в поезде и число обращений обращений пассажиров к системе покупки билетов.
Следующие k строк содержат по два натуральных числа Li и Ri (1 ≤ Li < Ri ≤ n) — начальная и конечная станции в i-м обращении к системе.
Выходные данные
Для каждого запроса на покупку билета в своей строке выведите ответ системы: число билетов, которые можно купить на данный маршрут, или 0, если ни одного билета купить нельзя.
Пример входных и выходных данных
| Ввод |
Вывод |
5 2 4
1 4
1 3
2 5
3 5 |
2
1
0
1 |