Description

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 $A$ and would like to hop onto a lily pad numbered $B$. She can take a giant hop of length $K$, 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 $A$ to $B$. But sometimes, she would like to know the second fewest number of hops needed.

Input Format

The first line of input contains a single integer, $A$, the starting lily pad ($-10^{18} \le A \le 10^{18}$).

The second line of input contains a single integer, $B$, the ending lily pad ($-10^{18} \le B \le 10^{18}$).

The third line of input contains a single integer, $K$, the distance of a giant hop ($2 \le K \le 10^{18}$).

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

Output Format

On a single line, output:

• the fewest number of hops, if $T = 1$
• the second fewest number of hops, if $T = 2$

required to move from lily pad $A$ to lily pad $B$.

0
10
3
1

4

0
11
4
1

4

0
11
4
2

5

0
0
3
1

0

Hint

Explanation of Output for Sample Input 1

Samantha hops to lily pads labeled $3$, $6$, and $9$, with three giant hops, and then hops to the lily pad labeled $10$ with one baby hop.

Explanation of Output for Sample Input 2

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

Explanation of Output for Sample Input 3

The fewest number of hops needed ($4$) was found in Sample 2. In this input, the second fewest number of steps is to be found, since $T = 2$. Samantha hops to lily pads labeled $4$ and $8$ with two giant hops, and then hops to the lily pad labeled $11$ 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.