Magical Creatures

The famous British magizoologist Newt Scamander owns a magical suitcase. Newt cast an Undetectable Extension Charm on it and kept inside a large collection of rare, endangered magical creatures he found during his trips around the world. One day Newt left the suitcase half open, and the creatures decided to escape. They cannot all leave at once, because the opening of the suitcase is very narrow. Each pet needs $s$ time units to climb out. The first pet leaves at time $t$, and the following pets leave at times $t + s$, $t + 2 \cdot s$, and so on. Newt learned about the creatures' clever plan too late. Now he wants to know the total number of creatures that escaped during the time intervals $[a_i, b_i]$, endpoints included. The suitcase holds an infinite number of pets. The answer for each interval is computed independently of the others.

The first line contains the integers $t$ and $s$, the moment when the first pet left the suitcase and the time between consecutive escapes ($0 \le t \le 10^{12}$, $1 \le s \le 10^{12}$). The second line contains $n$, the number of time intervals Newt is interested in ($1 \le n \le 100000$). Each of the next $n$ lines contains $a_i$ and $b_i$, the left and right bounds of the $i$-th interval ($0 \le a_i, b_i \le 10^{12}$).

Print a single number, the total number of creatures that escaped during the given intervals. The answer for each interval is computed independently of the others.

In the first test, the creatures escape at times 7, 10, and 13, all of which belong to the second interval. No creature escapes during the first interval.