题目描述

斗地主大师有P个欢乐豆，他想要恰好得到Q个欢乐豆。他可以进行两种操作：

1. 赢一把：欢乐豆数量变为原来的Y倍
2. 输一把：损失X个欢乐豆（当前欢乐豆数量≥X时才可执行） 他一天最多打52把斗地主，请求出最少需要打多少把才能将P个欢乐豆变为Q个，若52次内无法完成则输出Failed。

限制条件

• 时间限制：1000ms
• 内存限制：65536KB

输入说明

第一行输入4个正整数P、Q、X、Y，满足： $0 < P,X,Q \leq 2^{31}$，$1 < Y \leq 225$

输出说明

输出一个整数表示最少操作次数；若52次内无法完成，输出Failed。

样例输入

# 样例1
2 2333 666 8
# 样例2
1264574 285855522 26746122 3

样例输出

# 样例1
Failed
# 样例2
33

提示

可以考虑使用深度优先搜索，注意使用long long类型避免溢出。