Thời Hoàng Kim

Cho bốn số nguyên $x$, $y$, $l$, $r$. Một năm có số $n$ được gọi là năm xui xẻo nếu tồn tại hai số nguyên không âm $a$ và $b$ sao cho:

$$n=x^a+y^b.$$

Ví dụ, với $x=2$ và $y=3$ thì năm $4$ và năm $17$ đều xui xẻo ($4=2^0+3^1$, $17=2^3+3^2=2^4+3^0$), còn năm $18$ thì không vì không thể biểu diễn được như trên.

Một khoảng năm liên tiếp mà trong đó không có năm xui xẻo nào được gọi là một Thời Hoàng Kim.

Hãy tìm độ dài lớn nhất của một Thời Hoàng Kim nằm hoàn toàn trong đoạn $[l,r]$ (bắt đầu không sớm hơn năm $l$ và kết thúc không muộn hơn năm $r$). Nếu mọi năm trong đoạn $[l,r]$ đều xui xẻo thì đáp án là $0$.

Dữ liệu vào

Một dòng duy nhất chứa bốn số nguyên $x$, $y$, $l$, $r$.

Dữ liệu ra

In ra một số nguyên là độ dài lớn nhất của Thời Hoàng Kim trong đoạn $[l,r]$, hoặc $0$ nếu không tồn tại.

Ràng buộc

• $2\le x,y\le {10}^{18}$
• $1\le l\le r\le {10}^{18}$

Ví dụ