说明

青蛙萨曼莎在排成一条直线、等间距分布的荷叶间跳跃。荷叶的数量是无限的。荷叶按顺序用整数编号。每个整数都对应一片荷叶。

萨曼莎从编号为 $A$ 的荷叶出发，想要跳到编号为 $B$ 的荷叶。她可以做出长度为 $K$ 的大跳跃，或者长度为 $1$ 的小跳跃。每次跳跃既可以向前也可以向后。

萨曼莎想知道从 $A$ 到 $B$ 所需的最少跳跃次数。但有时，她也想知道第二少的跳跃次数。

输入格式

输入的第一行包含一个整数 $A$，表示起始荷叶的编号（$-10^{18} \le A \le 10^{18}$）。

第二行包含一个整数 $B$，表示目标荷叶的编号（$-10^{18} \le B \le 10^{18}$）。

第三行包含一个整数 $K$，表示一次大跳跃的距离（$2 \le K \le 10^{18}$）。

第四行包含一个整数 $T$，取值为 $1$ 或 $2$，表示需要求出最少（当 $T = 1$ 时）还是第二少（当 $T = 2$ 时）的步数。

输出格式

输出一行，包含：

• 如果 $T = 1$，输出最少的跳跃次数；
• 如果 $T = 2$，输出第二少的跳跃次数。

0
10
3
1

4

0
11
4
1

4

0
11
4
2

5

0
0
3
1

0

提示

样例输入 1 的输出解释

萨曼莎用三次大跳跃跳到编号为 $3$、$6$ 和 $9$ 的荷叶，然后用一次小跳跃跳到编号为 $10$ 的荷叶。

样例输入 2 的输出解释

萨曼莎用三次大跳跃跳到编号为 $4$、$8$ 和 $12$ 的荷叶，然后用一次（向后的）小跳跃跳到编号为 $11$ 的荷叶。

样例输入 3 的输出解释

最少的跳跃次数（$4$）已在样例 2 中得到。由于 $T = 2$，本输入需要求出第二少的步数。萨曼莎用两次大跳跃跳到编号为 $4$ 和 $8$ 的荷叶，然后用三次小跳跃跳到编号为 $11$ 的荷叶。

以下表格显示了 15 分是如何分配的：

注意，要获得满分，解决方案需要处理 64 位整数。例如：

• 在 C/C++ 中，应使用 long long 类型；
• 在 Java 中，应使用 long 类型。

翻译由 DeepSeek 完成