Arithmetic Coding
You have just received an assignment from Kitten Computing, a renowned software developer. You're thrilled because many of your friends have tried to get in before, but they either didn't pass the interview or couldn't complete their first assignment and were let go within the first month.
Now, you've been given your first task as part of a team working on new arithmetic coding software. In arithmetic coding, the string to be encoded is mapped to an interval (α, β) on the real line, and any fraction p/q within this interval serves as the encoding result.
Your goal is to find the fraction p/q such that both the numerator and denominator are as small as possible, given the rational numbers α and β. You don't need to worry about how α and β are generated; another team member has developed the software for that.
Input
Each line contains four integers P_1, Q_1, P_2, Q_2, where α = P_1/Q_1 and β = P_2/Q_2. All numbers are non-negative and do not exceed 10^18, and the denominators Q_1 and Q_2 are non-zero. It is guaranteed that α ≤ β. The input data contains no more than 10^4 lines.
Output
For each input line, output two natural numbers - P and Q, separated by a single space, such that α < P/Q < β. Here, Q should be as small as possible. If there are multiple optimal Q, choose the fraction with the smallest P.