이상한 기계

고고학자들이 고대 문명이 남긴 이상한 기계를 발견했다. 이 기계에는 두 정수 $x$와 $y$를 출력하는 두 부분이 있다.

기계를 조사한 고고학자들은 이 기계가 과거의 어느 시점부터 시작하여 시점 $t$에 대한 정보를 출력하는 특별한 시계라고 결론지었다. 시점 $t$에서 첫 번째 출력 부분은 정수 $x = ((t + \lfloor t/B \rfloor) \bmod A)$를 출력하고, 두 번째 출력 부분은 정수 $y = (t \bmod B)$를 출력한다. ($\lfloor x \rfloor$는 $x$ 이하이면서 가장 큰 정수를 나타낸다.)

분석 결과 이 기계는 항상 동작하지는 않으며, $n$개의 연속된 구간 $[l_i, r_i]$에서만 동작한다는 것을 알아냈다. 앞으로의 연구를 위해 고고학자들은 당신에게 이 기계가 출력하는 순서쌍 $(x, y)$ 중 서로 다른 것이 모두 몇 개인지 알아내는 프로그램을 작성해 달라고 부탁했다.

두 순서쌍 $(x_1, y_1)$과 $(x_2, y_2)$는 $x_1 \ne x_2$이거나 $y_1 \ne y_2$이면 서로 다르다.

첫 줄에는 세 정수 $n$, $A$, $B$가 주어진다. ($1 \le n \le 10^6$; $1 \le A, B \le 10^{18}$)

다음 $n$줄의 각각에는 두 정수 $l_i$와 $r_i$가 주어지는데, 이 기계가 동작하는 구간 $[l_i, r_i]$의 시작 시점과 종료 시점을 나타낸다. ($0 \le l_i \le r_i \le 10^{18}$, $r_i < l_{i+1}$)

이 기계가 동작하는 동안 출력하는 서로 다른 순서쌍 $(x, y)$의 수를 출력한다.

첫 번째 테스트에서, 이 기계는 시점 4에서 $(2, 1)$을, 시점 7에서 $(0, 1)$을, 시점 8에서 $(1, 2)$를, 시점 9에서 $(0, 0)$을, 시점 17에서 $(1, 2)$를, 시점 18에서 $(0, 0)$을 출력한다. 따라서 서로 다른 네 개의 순서쌍 $(0, 0), (0, 1), (1, 2), (2, 1)$을 출력한다.