마법 생물

영국의 유명한 마법동물학자 뉴트 스캐맨더에게는 마법 여행 가방이 있다. 뉴트는 이 가방에 비가시 확장 주문을 걸어 두었고, 세계 일주를 하며 모은 희귀하고 멸종 위기에 처한 마법 생물을 가득 넣어 두었다. 어느 날 뉴트가 가방을 반쯤 열어 둔 채 나갔고, 생물들은 탈출하기로 했다. 가방의 입구가 매우 좁아서 생물들은 동시에 빠져나갈 수 없다. 생물 한 마리가 가방 밖으로 나오는 데 $s$의 시간이 걸린다. 첫 번째 생물은 시각 $t$에 나오고, 그다음 생물은 $t + s$, $t + 2 \cdot s$ 순서로 같은 간격을 두고 차례로 나온다. 뉴트는 생물들의 영리한 계획을 너무 늦게 알아챘다. 이제 그는 구간 $[a_i, b_i]$ (양 끝 포함) 동안 탈출한 생물의 총 수를 알고 싶어 한다. 가방 속 생물은 무한히 많다. 각 구간의 답은 다른 구간과 독립적으로 계산한다.

첫 줄에 정수 $t$와 $s$가 주어진다. $t$는 첫 번째 생물이 가방에서 나온 시각이고, $s$는 연속된 탈출 사이의 시간 간격이다 ($0 \le t \le 10^{12}$, $1 \le s \le 10^{12}$). 둘째 줄에는 뉴트가 관심을 가지는 시간 구간의 개수 $n$이 주어진다 ($1 \le n \le 100000$). 이어지는 $n$개의 줄에는 $i$번째 구간의 왼쪽 끝 $a_i$와 오른쪽 끝 $b_i$가 주어진다 ($0 \le a_i, b_i \le 10^{12}$).

주어진 구간들 동안 탈출한 생물의 총 수를 한 줄에 출력한다. 각 구간의 답은 다른 구간과 독립적으로 계산한다.

첫 번째 테스트에서 생물들은 시각 7, 10, 13에 탈출하며, 이 시각들은 모두 두 번째 구간에 속한다. 첫 번째 구간에서는 탈출하는 생물이 없다.