Как известно, у одного из самых известных магозоологов Великобритании Ньюта Саламандера имеется волшебный чемодан. На чемодан Ньют наложил Заклинание незримого расширения, а внутри него хранил обширную коллекцию редких, находящихся под угрозой исчезновения волшебных существ, найденных им во время кругосветных путешествий.
Однажды Ньют оставил свой чемодан полуоткрытым, и существа решили совершить побег. Однако сделать это одновременно они не могут, так как створки чемодана очень узкие. Время, необходимое каждому питомцу для того, чтобы вылезти из чемодана , составляет s. Первый из питомцев покидает чемодан в момент времени t, а последующие — в моменты времени t + s, t + 2·s и так далее.
Ньют Саламандер слишком поздно узнал о хитром плане питомцев, и сейчас его интересует, какое суммарное количество существ сбежало из чемодана в промежутки времени [ai, bi], включая границы. Питомцев в волшебном чемодане содержится бесконечное количество.
В первой строке входного файла заданы числа t и s — момент времени, когда первый питомец покинул чемодан, и интервал времени между побегами питомцев соответственно (0 ≤ t ≤ 1012, 1 ≤ s ≤ 1012).
Во второй строке содержится число n — количество интересующих Саламандера отрезков времени (1 ≤ n ≤ 100 000). В следующих n строках содержатся числа ai, bi — левая и правая границы i-го отрезка времени (0 ≤ ai, bi ≤ 1012).
В выходном файле выведите единственное число — суммарное количество существ, сбежавших во время данных промежутков времени. Ответ для каждого промежутка считается независимо от других промежутков.
4 3
2
1 3
5 13
3
1 10
3
1 1
1 1
1 1
3
В первом тесте из условия существа сбегают в моменты времени 7, 10 и 13, принадлежащие второму промежутку времени. Во время первого промежутка ни одно существо не совершает побег.