Арифметичне кодування
Ви отримали своє перше завдання від 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.