Berland 的不吉利年份是指其编号 n 可以表示为 n = xa + yb 的年份,其中 a 和 b 为非负整数。
例如,如果 x = 2 且 y = 3,则第 4 年和第 17 年不吉利(4 = 20 + 31, 17 = 23 + 32 = 24 + 30),而第 18 年则不吉利,因为没有这样的表示。
这样的年份间隔,其中没有不吉利的年份,称为黄金时代。
你应该编写一个程序来找到黄金时代的最大长度,该长度不早于 l 年开始,不晚于 r 年结束。如果 [l, r] 区间内的所有年份都不吉利,则答案为 0。
输入
第一行包含四个整数 x、y、l 和 r (2 ≤ x, y ≤ 1018, 1 ≤ l ≤ r ≤ 1018)。
输出
打印区间 [l, r] 内《黄金时代》的最大长度。
如果区间 [l, r] 中的所有年份都不吉利,则打印 0。
示例
输入 #1
2 3 1 10
输出 #1
1
输入 #2
3 5 10 22
输出 #2
8
输入 #3
2 3 3 5
输出 #3
0
注意
在第一个示例中,不幸的年份是 2、3、4、5、7、9 和 10。因此,黄金时代的最大长度在区间 [1, 1]、[6, 6] 和 [8, 8] 中实现。
在第二个示例中,最长的黄金时代是区间 [15, 22]。