Aritmetik kodlaşdırma
Siz Kitten Computing, məşhur proqram təminatı inkişaf etdiricisindən yeni bir tapşırıq almısınız. Bu sizin üçün böyük bir şansdır, çünki bir çox dostlarınız əvvəllər ora müraciət etmiş, lakin ya müsahibədən keçə bilməmiş, ya da ilk tapşırıqlarını yerinə yetirə bilməyərək işlərinin ilk ayında işdən çıxarılmışdılar.
İndi siz də öz ilk tapşırığınızı almısınız və yeni arifmetik kodlaşdırma üçün proqram təminatı hazırlayan komandada çalışırsınız. Xatırladaq ki, arifmetik kodlaşdırma zamanı kodlaşdırılmalı olan sıra, real sıranın (α, β) intervalına çevrilir və sonra bu intervalda olan hər hansı bir p/q kəsiri kodlaşdırmanın nəticəsi olur.
Sizin tapşırığınız bu p/q kəsirini tapmaqdır ki, verilmiş rasional ədədlər α və β üçün surət və məxrəc mümkün qədər kiçik olsun. Sizə α və β mənşəyi barədə narahat olmaq lazım deyil: bu ədədləri yaratmaq üçün proqram təminatını sizin komandanızdan başqa bir şəxs yazıb.
Giriş verilənləri
Hər bir sıra dörd tam ədəd P_1, Q_1, P_2, Q_2 ehtiva edir ki, burada α = P_1/Q_1 və β = P_2/Q_2. Bütün ədədlər qeyri-mənfi və 10^18 -dən böyük deyil, məxrəc Q_1 və Q_2 sıfırdan fərqlidir. α ≤ β təmin edilir. Giriş məlumatları ən çox 10^4 sıra ehtiva edir.
Çıxış Məlumatları
Hər bir giriş sırası üçün iki təbii ədəd - P və Q, bir boşluqla ayrılmış şəkildə çıxarın ki, α < P/Q < β. Bu halda Q mümkün olan ən kiçik olmalıdır. Əgər bir neçə optimal Q varsa, ən kiçik P olan kəsiri çıxarın.