Андрійко та суп із фрикадельками

Обмеження: 4 сек., 256 МіБ

Усі ми знаємо про Андрійкову любов до фрикадельок. І цього разу він вирішив влаштуватися кухарем в місцевий ресторан «0.5».

Та не все в нього виходило добре, першого свого робочого дня він зробив тільки \(a\) фрикадельок. Та з кожним днем він покращував свої вміння і виготовляв в \(a\) разів більше фрикадельок, ніж попереднього дня.

За традицією в ресторані «0.5» в кожному супі має бути рівно \(n\) фрикадельок. Шеф цього ресторану щодня хоче приготувати найбільшу можливу кількість супів, бо відвідувачів у такому чудовому закладі багато, і всі чомусь приходять саме по суп. Але все ж кожного дня залишається деяка кількість фрикадельок, яку Андрійко може забрати додому.

На \(l\)-ий день своєї роботи Андрійко зрозумів, що найбільша кількість м’ясних виробів, які він може забрати з собою за один день, рівна \(n-1\), і такі дні Андрійко почав називати щасливими.

Вам потрібно порахувати, скільки буде щасливих днів на проміжку від \(l\)-го до \(r\)-го дня включно.

Вхідні дані

У першому рядку задані два цілі числа \(a\) та \(n\) — кількість фрикадельок першого дня та кількість днів.

У другому рядку задані два цілі числа \(l\) і \(r\) — межі проміжку.

Вихідні дані

Єдине число — кількість щасливих днів від \(l\)-го до \(r\)-го дня включно.

Обмеження

\(1 \le a < n \le 10^{14}\),

\(1 \le l \le r \le 10^{18}\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 5 4 7	1

Примітки

Першого дня Андрійко виготовить 3 фрикадельки, і вони в нього залишаться.

Другого дня він виготовить 9 фрикадельок, і в нього залишаться 4. Цей день буде щасливим.

Також щасливим буде 6-ий день, який і належить проміжку \([4; 7]\).