Minimum Original Numbers for Maximum Annihilation

We define an operation \(op\) on an integer \(x\) as follows:

\[ op(x)=\left\lfloor \frac{x}{d} \right\rfloor, \]

where \(d\) is a given positive integer. An original number is a special number that is immune to being "annihilated." A number \(x\) is said to be annihilated by an original number \(a\) if, after applying the \(op\) operation zero or more times on \(x\), it becomes equal to \(a\); that is, if there exists a nonnegative integer \(k\) such that

\[ op^{(k)}(x)=a. \]

Note that when \(d=1\), we have \(op(x)=x\) (i.e. the chain of operations on \(x\) is just \(\{x\}\)), so an original number \(a\) can only annihilate \(x\) if \(x=a\).

SY has access to \(m\) original numbers that can be chosen arbitrarily. For a given interval \([l, r]\) (with \(l\) and \(r\) given), SY wants to annihilate as many numbers in the interval as possible by selecting some of these original numbers. In other words, if an original number \(a\) is selected, then every integer \(x\) in \([l, r]\) whose chain (\(x, op(x), op^{(2)}(x), \dots\)) contains \(a\) is annihilated. Note that an original number is never annihilated even if it itself lies in \([l, r]\).

Your task is to determine the minimum number of original numbers that need to be chosen (from the available collection of \(m\) numbers) so that the number of annihilated numbers in the interval \([l, r]\) is maximized.

Observation:

• If \(d>1\), then for any positive integer \(x\) the chain \(x, op(x), op^{(2)}(x), \dots\) eventually reaches \(0\) because dividing by \(d\) repeatedly yields 0. Thus, by selecting \(0\) as an original number, every number in \([l, r]\) (regardless of \(l\) and \(r\)) is annihilated. Hence, when \(d>1\) the answer is always 1 (assuming at least one original number is available).
• If \(d=1\), then \(op(x)=x\). Therefore, an original number \(a\) can only annihilate the number \(a\) itself. In this case, the maximum number of annihilated numbers is \(\min(m, r-l+1)\) (you cannot annihilate more numbers than the number of available original numbers, and each chosen original number annihilates exactly one number in \([l, r]\)). Thus, the minimum number of original numbers required is \(\min(m, r-l+1)\).

Given the 4 input integers \(d\), \(m\), \(l\), and \(r\), output the required minimum number of original numbers.

inputFormat

The input consists of a single line containing four space-separated integers:

• d (the divisor in the \(op\) operation),
• m (the number of available original numbers),
• l (the lower bound of the interval), and
• r (the upper bound of the interval).

It is guaranteed that all numbers are nonnegative integers and \(d\) is at least 1. You may assume that at least one original number is available (i.e. \(m\ge1\)).

outputFormat

Output a single integer: the minimum number of original numbers needed to annihilate the maximum possible number of integers in the interval \([l, r]\).

Note:

• If \(d > 1\), output 1.
• If \(d = 1\), output \(\min(m, r-l+1)\).

sample

2 5 10 20

1