题目描述

Iroha 对养宠物的游戏很感兴趣。

Iroha 的宠物是 Takahashi。初始时，Takahashi 的 STR 和 EXP 分别为 $X$ 和 $0$。这两个参数会在以下两种训练中增加：

• 去 Kakomon Gym：STR 乘以 $A$，EXP 增加 $1$。
• 去 AtCoder Gym：STR 增加 $B$，EXP 增加 $1$。

当 Takahashi 的 STR 变为 $Y$ 或更高时，他将进化，但 Iroha 认为这样会让他变得不那么可爱。

找出在不让 Takahashi 进化的情况下，他的最大可能 EXP。

约束条件

• $1 \\leq X < Y \\leq 10^{18}$
• $2 \\leq A \\leq 10^9$
• $1 \\leq B \\leq 10^9$
• 输入的所有值都是整数。

输入

输入以以下格式从标准输入中给出：

$X$ $Y$ $A$ $B$

输出

打印在给定情况下 Takahashi 的最大可能 EXP。

示例输入 1

4 20 2 10

示例输出 1

2

初始时，Takahashi 的 STR 为 $4$。我们可以通过以下训练过程使他的 EXP 变为 $2$：

• 首先，去 Kakomon Gym，使他的 STR 变为 $8$，EXP 变为 $1$。
• 然后，去 AtCoder Gym，使他的 STR 变为 $18$，EXP 变为 $2$。

另一方面，没有办法训练他使他的 EXP 变得大于 $2$。

示例输入 2

1 1000000000000000000 10 1000000000

示例输出 2

1000000007

注意防止溢出。