Frog Meeting on a Circular Latitude

Two frogs, Frog A and Frog B, met online and decided to meet in person. They discovered that they both live on the same latitude and agreed to jump westwards (the positive direction on our number line) until they meet. However, they started jumping without clarifying each other’s features or the meeting spot. Being optimistic, they believe that if they keep jumping, eventually they will land on the same point at the same time.

We model the latitude as a circular number line with circumference \(L\) meters. The point at 0° east longitude is the origin, and positions increase towards the west. Frog A starts at coordinate \(x\) and Frog B at coordinate \(y\). In one jump, Frog A covers \(m\) meters and Frog B covers \(n\) meters. Both frogs take the same time per jump. After \(k\) jumps, the positions of the frogs are given by:

[ \text{Position of A} = (x + k \cdot m) \bmod L, \quad \text{and} \quad \text{Position of B} = (y + k \cdot n) \bmod L. ]

The frogs meet if and only if they land on the exact same position at the same time. Your task is to determine the minimum number \(k\) of jumps after which they will meet. If they cannot meet, output -1.

Hint: The condition for meeting can be formulated as finding the smallest non-negative integer \(k\) satisfying:

[ x + k \cdot m \equiv y + k \cdot n \pmod{L} \quad \Longleftrightarrow \quad k (m - n) \equiv (y - x) \pmod{L}. ]

If \(m = n\), then the frogs meet only when \(x \equiv y \pmod{L}\).

inputFormat

The input consists of a single line containing five space-separated integers: \(x\), \(y\), \(m\), \(n\), and \(L\), which represent the starting position of Frog A, the starting position of Frog B, the jump distance of Frog A, the jump distance of Frog B, and the total length of the latitude line (in meters), respectively.

outputFormat

Output a single integer representing the minimum number of jumps \(k\) after which both frogs land on the same point simultaneously. If they can never meet, output -1.

sample

0 0 5 3 20

0