#215641. [CCC 2026 S1] Baby Hop, Giant Hop

Samantha the Frog is hopping between lily pads arranged in a straight line, evenly spaced. There are an infinite number of lily pads. The lily pads are numbered, in order, using integers. For every integer, there is also a lily pad.

Samantha starts on a lily pad numbered and would like to hop onto a lily pad numbered . She can take a giant hop of length , or a baby hop of length 1. Each hop can be either forwards or backwards.

Samantha would like to know the fewest number of hops needed to get from to . But sometimes, she would like to know the second fewest number of hops needed.

The first line of input contains a single integer, , the starting lily pad ().

The second line of input contains a single integer, , the ending lily pad ().

The third line of input contains a single integer, , the distance of a giant hop ().

The fourth line of input contains the integer, , which is either 1 or 2, indicating if the fewest (when ) or second fewest (when ) number of steps should be found.

On a single line, output:

• the fewest number of hops, if
• the second fewest number of hops, if

required to move from lily pad to lily pad .

样例输入 1

0
10
3
1

样例输出 1

4

样例输入 2

0
11
4
1

样例输出 2

4

样例输入 3

0
11
4
2

样例输出 3

5

样例输入 4

0
0
3
1

样例输出 4

0

Explanation of Output for Sample Input 1

Samantha hops to lily pads labeled , , and , with three giant hops, and then hops to the lily pad labeled with one baby hop.

Explanation of Output for Sample Input 2

Samantha hops to lily pads labeled , , and , with three giant hops, and then hops to the lily pad labeled with one (backwards) baby hop.

Explanation of Output for Sample Input 3

The fewest number of hops needed () was found in Sample 2. In this input, the second fewest number of steps is to be found, since . Samantha hops to lily pads labeled and with two giant hops, and then hops to the lily pad labeled with three baby hops.

The following table shows how the 15 available marks are distributed:

Note that for full marks, solutions will need to handle 64-bit integers. For example:

• in C/C++, the type long long should be used;
• in Java, the type long should be used.