Numbers with a Given Remainder

Version: Phuoc Hung OJ Extended

Problem Statement

Given integers $L,R,M,r$ with $L\le R$ and $0\le r<M$, count the integers $X$ in $[L,R]$ such that $X\equiv r\pmod M$.

Input

One line contains four integers $L$, $R$, $M$, and $r$.

Output

Print the number of integers satisfying the condition.

Subtasks

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

Examples

Example 1

Input

1 20 5 2

Output

4

Explanation

The integers with remainder $2$ modulo $5$ are $2,7,12,17$, so the answer is $4$.

Example 2

Input

1 20 5 0

Output

4

Explanation

Remainder $0$ corresponds to multiples $5,10,15,20$, giving $4$ integers.

Example 3

Input

8 8 10 8

Output

1

Explanation

The interval contains only $8$, and $8\bmod10=8$, so exactly one integer is valid.