2. Switching TV-Channels
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Lisa's parents subscribed to a TV package containing $$$N$$$ TV channels, numbered from $$$1$$$ to $$$N$$$.

There are two buttons for switching channels on the remote control: "$$$+$$$" and "$$$-$$$".

A short press of button "$$$+$$$" switches to the next channel, if the current channel number is less than $$$N$$$. If the current channel number is equal to $$$N$$$, the TV continues to show that channel. If the button "$$$+$$$" is pressed and held for a while and the current TV-channel number is no more than $$$N - K$$$, it will switch to $$$K$$$ channels forward. Otherwise, a switch to channel $$$N$$$ occurs.

Similarly, pressing the button "$$$-$$$" shortly switches to the previous channel, if the current channel number is greater than $$$1$$$. If the current channel number equals $$$1$$$, the TV continues to show that channel. If the button "$$$-$$$" is pressed and held for some time and the current channel number is greater than $$$K$$$, it will switch to $$$K$$$ channels backward. Otherwise, a switch to channel $$$1$$$ occurs.

When Lisa turned on the TV, channel $$$P$$$ was on. Lisa knows that an interesting program will start soon on channel $$$U$$$. Estimate the minimum number of button presses on the TV remote control that Lisa needs to make in order to switch the TV to channel $$$U$$$.

Input

The first line contains an integer $$$N$$$ ($$$3 \le N \le 10^9$$$) which stands for the number of TV channels.

The second line contains an integer $$$K$$$ ($$$2 \le K \lt N$$$), which is the number of channels which are switched backward or forward when holding the corresponding switch button on the TV-controller.

The third line contains an integer $$$P$$$ ($$$1 \le P \le N$$$), which denotes the channel number that was on TV initially.

The fourth line contains an integer $$$U$$$ ($$$1 \le U \le N$$$), which is the channel number that Lisa wants to switch to.

It should be assumed that $$$P \neq U$$$.

Output

You should output a single integer, which stands for the minimum number of times one should press the TV-controller buttons required to switch from channel $$$P$$$ to channel $$$U$$$.

Scoring

Solutions that run correctly for $$$P \lt U$$$, $$$N \le 100$$$ score $$$24$$$ points.

Solutions that run correctly for $$$N \le 100$$$ score $$$48$$$ points.

Examples
Input
20
5
3
19
Output
4
Input
20
5
3
17
Output
4
Input
20
5
14
12
Output
2
Input
20
5
3
16
Output
4
Note

According to the first example, Lisa should first press the button "$$$+$$$" shortly and switch from channel 3 to channel 4, and then switch by 5 channels forward for three times. That is, first switch from channel 4 to channel 9, then from channel 9 to channel 14, and finally from channel 14 to channel 19.

In the second example, Lisa can first switch to channel 2 with a short press on the button "$$$-$$$", and then switch forward by 5 channels for 3 times, so that she switches first from channel 2 to channel 7, then from channel 7 to channel 12, and finally from channel 12 to channel 17.

In the third example, Lisa should press the button "$$$-$$$" shortly 2 times.

In the fourth example, Lisa needs to first switch backward to channel 1 holding the "$$$-$$$" button, and then switch forward three times, switching sequentially from channel 1 to channels 6, 11, and then 16.