Maintenance Milestones

Version: Phuoc Hung OJ Extended

Problem Statement

A device is first serviced on day $A$. It is then serviced every $K$ days, so service days are $A,A+K,A+2K,\ldots$. Given the day interval $[L,R]$, count the service events in the interval.

Input

One line contains four integers $A$, $K$, $L$, and $R$.

Output

Print the number of service events whose day lies in $[L,R]$.

Subtasks

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

Examples

Example 1

Input

3 7 10 30

Output

3

Explanation

The milestones are $3,10,17,24,31,\ldots$. The interval $[10,30]$ contains $10,17,24$, so the answer is $3$.

Example 2

Input

5 10 5 5

Output

1

Explanation

Day $5$ is the first service day and lies in the interval, so the answer is $1$.

Example 3

Input

100 25 101 199

Output

3

Explanation

After day $100$, the milestones are $125,150,175,200,\ldots$; the interval contains $125,150,175$, for a total of $3$.