Number of Representable Numbers#4572

Number of Representable Numbers

1 second

256 megabytes

Medium

Given two non-negative integers $a$ and $b$ .

A number $x$ is called representable if it can be written as a sum $x = x_{1} + x_{2} + \dots + x_{n}$ x = x_1 + x_2 + \ldots + x_n for some finite (possibly zero) number of terms, where each term $x_{i}$ x_i is equal to either $a$ or $b$ . Determine how many distinct numbers in the interval $[A, B]$ are representable.

Constraints

$a, b, A, B$ a, b, A, B are integers. $0 \leq a, b \leq 10000$ 0 \leq a, b \leq 10\ 000 $0 \leq A \leq B \leq 1 0^{7}$ 0 \leq A \leq B \leq 10^7

Input

The input consists of a single line containing $a$ , $b$ , $A$ , $B$ .

Output

Output the number of representable numbers using $a$ and $b$ in the interval $[A, B]$ .

Examples

Example 1

Loading

x = x_{1} + x_{2} + \dots + x_{n}

x_{i}

a, b, A, B

0 \leq a, b \leq 10000

0 \leq A \leq B \leq 1 0^{7}