Số có số dư cho trước (Numbers with a Given Remainder)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho bốn số nguyên $L,R,M,r$ thỏa mãn $L\le R$ và $0\le r<M$. Hãy đếm số lượng số nguyên $X$ trong đoạn $[L,R]$ có số dư bằng $r$ khi chia cho $M$, tức là $X\equiv r\pmod M$.

Input

Một dòng chứa bốn số nguyên $L$, $R$, $M$ và $r$.

Output

In ra số lượng số nguyên thỏa mãn yêu cầu.

Subtask

• Subtask 1 (30 điểm):
  • $1 \le L \le R \le 10^6$.
  • $1 \le M \le 10^{18}$.
  • $0 \le r < M$.
• Subtask 2 (70 điểm):
  • $1 \le L \le R \le 10^{18}$.
  • $1 \le M \le 10^{18}$.
  • $0 \le r < M$.

Ví dụ

Ví dụ 1

Input

1 20 5 2

Output

4

Giải thích

Các số có số dư $2$ khi chia cho $5$ là $2,7,12,17$, nên kết quả là $4$.

Ví dụ 2

Input

1 20 5 0

Output

4

Giải thích

Số dư $0$ tương ứng với các bội $5,10,15,20$, có $4$ số.

Ví dụ 3

Input

8 8 10 8

Output

1

Giải thích

Đoạn chỉ có số $8$ và $8\bmod10=8$, nên có đúng một số thỏa mãn.