Количество представимых High

Заданы два целых числа a и b. Число x назовем представимым, если его можно представить в виде суммы x = x_1 + x_2 + ... + x_n конечного (возможно нулевого) числа слагаемых x_i, каждое из которых равно a или b. Требуется определить, сколько различных чисел на отрезке [A, B] являются представимыми.

Ограничения

a, b – целые числа, не превосходящие по модулю 10000. A, B – целые числа, не превосходящие по модулю 10^18. A ≤ B.

Входные данные

В единственной строке содержатся числа a, b, A, B.

Выходные данные

Выведите количество представимых через a и b чисел из отрезке [A, B].

Примеры