Ancient Clock Display Distinct Pairs

Archaeologists have discovered a strange device left by an ancient civilization. The device has two screens that display two integers \(x\) and \(y\). After extensive research, scientists concluded that the device is a special clock. It measures the elapsed time \(t\) from some starting moment and displays the numbers \(x\) and \(y\) in a peculiar manner. Specifically, if the elapsed time is \(t\), the device shows:

[ \begin{aligned} x &= \Bigl( t + \left\lfloor \frac{t}{B} \right\rfloor \Bigr) \bmod A, \ y &= t \bmod B, \end{aligned} ]

where \(\lfloor x \rfloor\) denotes the floor function (i.e. the greatest integer less than or equal to \(x\)).

However, the device's screens only work during certain time intervals. Specifically, there are \(n\) consecutive time intervals during which the device works properly; the \(i\)-th interval starts at time \(l_i\) and ends at time \(r_i\) (inclusive). Your task is to determine how many different pairs \((x, y)\) can be displayed when the device's screens are working. Two pairs \((x_1, y_1)\) and \((x_2, y_2)\) are considered different if \(x_1 \neq x_2\) or \(y_1 \neq y_2\).

inputFormat

The first line of the input contains three integers \(A\), \(B\), and \(n\).

Then \(n\) lines follow. The \(i\)-th line contains two integers \(l_i\) and \(r_i\) representing the inclusive time interval during which the device works.

outputFormat

Output a single integer: the number of distinct pairs \((x, y)\) that can be displayed when the device is working.

sample

5 3 1
0 5

6