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.

The first line of input contains a single integer, \(A\), the starting lily pad \((-10^{18} \leq A \leq 10^{18})\).
The second line of input contains a single integer, \(B\), the ending lily pad \((-10^{18} \leq B \leq 10^{18})\).
The third line of input contains a single integer, \(K\), the distance of a giant hop \((2 \leq K \leq 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.
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.

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\).

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.