Fraction Magic

Time limit2sMemory limit1024 MB

Summary

Given fractions p1/q1 and p2/q2 and the denominator b of a/b, find the smallest integer numerator a with p1/q1 < a/b < p2/q2, or -1 if none exists.

Level: Easy2 of 10
Topics: Brute force, Math
Solved: No attempts yet

Statement

Sergey wants to learn juggling and magic tricks. A friend showed him a trick: Sergey picks a positive fraction $\frac{a}{b}$ , then names its denominator and two fractions $\frac{p_1}{q_1}$ and $\frac{p_2}{q_2}$ such that $\frac{p_1}{q_1} < \frac{a}{b} < \frac{p_2}{q_2}$ , and there is no smaller fraction with the same denominator as the one Sergey picked between them. The friend then guessed the numerator of Sergey's fraction.

Now Sergey wants to perform this trick himself. Write a program that finds the numerator of the chosen fraction.

Input

The input file contains three fractions, one per line, in the format /: $\frac{p_1}{q_1}$ , $\frac{a}{b}$ , $\frac{p_2}{q_2}$ . In place of $a$ , the input has a question mark <?>. All numerators and denominators are positive integers not exceeding 1000.

Output

Print the minimum integer $a$ such that $\frac{p_1}{q_1} < \frac{a}{b} < \frac{p_2}{q_2}$ . If no such integer exists, print $-1$ .

Examples2

Example 1
Input
```
1/2
?/8
3/4
```
Expected output
```
5/8
```
Example 2
Input
```
3/20
?/2
4/10
```
Expected output
```
-1
```