Strange Machine

Archaeologists have found a strange machine left behind by an ancient civilization. This machine has two parts that output two integers $x$ and $y$.

After examining the machine, the archaeologists concluded that it is a special clock that outputs information about a time $t$, starting from some point in the past. At time $t$, the first output part prints the integer $x = ((t + \lfloor t/B \rfloor) \bmod A)$, and the second output part prints the integer $y = (t \bmod B)$. ($\lfloor x \rfloor$ denotes the largest integer not greater than $x$.)

Analysis showed that the machine does not always work; it works only on $n$ consecutive intervals $[l_i, r_i]$. For further research, the archaeologists ask you to write a program that determines how many distinct ordered pairs $(x, y)$ the machine outputs.

Two ordered pairs $(x_1, y_1)$ and $(x_2, y_2)$ are different if $x_1 \ne x_2$ or $y_1 \ne y_2$.

The first line gives three integers $n$, $A$, $B$. ($1 \le n \le 10^6$; $1 \le A, B \le 10^{18}$)

Each of the next $n$ lines gives two integers $l_i$ and $r_i$, the start and end times of an interval $[l_i, r_i]$ on which the machine works. ($0 \le l_i \le r_i \le 10^{18}$, $r_i < l_{i+1}$)

Print the number of distinct ordered pairs $(x, y)$ the machine outputs while it works.

In the first test, the machine outputs $(2, 1)$ at time 4, $(0, 1)$ at time 7, $(1, 2)$ at time 8, $(0, 0)$ at time 9, $(1, 2)$ at time 17, and $(0, 0)$ at time 18. Thus it outputs four distinct ordered pairs: $(0, 0), (0, 1), (1, 2), (2, 1)$.