Mốc bảo dưỡng (Maintenance Milestones)

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

Đề bài

Một thiết bị được bảo dưỡng lần đầu vào ngày $A$. Sau đó, cứ đúng $K$ ngày thiết bị lại được bảo dưỡng một lần, nên các ngày bảo dưỡng là $A,A+K,A+2K,\ldots$. Cho khoảng ngày $[L,R]$. Hãy đếm số lần bảo dưỡng diễn ra trong khoảng này.

Input

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

Output

In ra số lần bảo dưỡng có ngày thuộc đoạn $[L,R]$.

Subtask

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

Ví dụ

Ví dụ 1

Input

3 7 10 30

Output

3

Giải thích

Dãy mốc là $3,10,17,24,31,\ldots$. Trong $[10,30]$ có $10,17,24$, nên kết quả là $3$.

Ví dụ 2

Input

5 10 5 5

Output

1

Giải thích

Ngày $5$ chính là mốc bảo dưỡng đầu tiên và nằm trong đoạn, nên kết quả bằng $1$.

Ví dụ 3

Input

100 25 101 199

Output

3

Giải thích

Các mốc sau $100$ là $125,150,175,200,\ldots$; trong đoạn có $125,150,175$, tổng cộng $3$ mốc.