Арифметическое кодирование
Вы только что получили задание от Kitten Computing, известного разработчика программного обеспечения. Вы не можете поверить в ваше счастье - множество ваших друзей подавали туда заявку раньше, но они либо провалились на интервью, либо не смогли выполнить их первое задание и были уволены в первый месяц их работы в Kitten Computing.
Сейчас вы и сами получили ваше первое задание, в команде которая разрабатывает программное обеспечение для нового арифметического кодирования. Напомним, что во время арифметического кодирования, строка, которую нужно закодировать, переходит в интервал (α, β) реальной строки, а затем любая дробь p/q на этом интервале и есть результат кодирования.
Ваше задание - найти эту дробь p/q так, чтобы числитель и знаменатель были как можно меньше, для заданных рациональных чисел α и β. Вам не нужно беспокоится о происхождении α и β: программное обеспечения для создания этих чисел написал другой человек из вашей команды.
Входные данные
Каждая строка содержит четыре целых числа P_1, Q_1, P_2, Q_2 таких, что α = P_1/Q_1 и β = P_2/Q_2. Все числа неотрицательные и не превышают 10^18, знаменатели Q_1 и Q_2 отличны от нуля. Гарантируется, что α ≤ β. Входные данные содержат не более 10^4 строк.
Выодные данные
Для каждой входной строки вывести два натуральных числа - P и Q, разделенные одним пробелом, такие, что α < P/Q < β. При этом Q должно быть минимально возможным. Если есть несколько оптимальных Q, выводите дробь с минимальным P.