eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Арифметическое кодирование

Арифметическое кодирование

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Вы только что получили задание от 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.

Пример

Входные данные #1
3 10 7 20
0 1 1 1
Выходные данные #1
1 3
1 2
Источник 2012 Харьков, Зимняя школа, День Сергея Копеловича, Задача C