Stone Bridge

Donggyu and Jumi are on a stone bridge that runs in a straight line. The stones are numbered 0 through 100,000. Donggyu stands on stone $N$ and Jumi stands on stone $M$.

To reach Jumi quickly, Donggyu brought two pogo sticks, one with power $A$ and one with power $B$. Crossing the bridge is turn based. In one turn Donggyu picks one of the following eight moves from his current stone $x$.

• Walk to $x - 1$ or $x + 1$.
• Hop with a pogo stick to $x - A$, $x + A$, $x - B$, or $x + B$.
• Gather his strength for an instant and move to stone $x \times A$ or stone $x \times B$.

For example, if Donggyu is on stone 7 and a pogo stick has power 8, he can hop to stone 15, or gather his strength and land on stone 56.

No stone is numbered below 0 or above 100,000, so he cannot move to such a position. He may use the same move as many times as he wants, and every input is a case where Jumi can be reached.

The first line contains the pogo stick powers $A$ and $B$, Donggyu's position $N$, and Jumi's position $M$, separated by spaces. ($2 \le A, B \le 30$, $0 \le N, M \le 100{,}000$)

Print the minimum number of moves Donggyu needs to reach Jumi.