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