Rasional Yaxınlaşma
Bir n dərəcəli p(x) polinomu, f(x) funksiyasını təqribən hesablamaq üçün, f(x)-in güc sırasının (x = 0 ətrafında genişlənmiş) ilk n əmsallarına uyğunlaşdırmaqla istifadə edilə bilər. Məsələn,
Təəssüf ki, polinomlar "gözəl"dir və onlar zəif davranan funksiyaları (məsələn, təkillikləri olanlar) təqribən hesablamaq üçün yaxşı işləmir. Bu problemi aradan qaldırmaq üçün, əvəzinə p(x)/q(x) formasında rasyonel funksiyalarla funksiyaları təqribən hesablaya bilərik, burada p(x) və q(x) polinomlardır. Sizdən Təqribən Hesablama Maşınları tərəfindən bu problemi həll etməyiniz istənilib ki, onlar sizin həllinizi öz təqribən hesablama proqramlarına daxil edə bilsinlər.
Verilən m, n və f(x)-in güc sırasının ilk m+n əmsalları ilə, biz p(x) və q(x) polinomlarını hesablamaq istəyirik ki, onların dərəcələri müvafiq olaraq ən çox m-1 və n-1 olsun, belə ki, q(x)·f(x)-p(x)-in güc sırası genişlənməsi 0 kimi ilk m+n-1 əmsallara və x^{m+n-1} terminə uyğun olaraq 1 əmsalına malik olsun. Başqa sözlə, biz p(x) və q(x) tapmaq istəyirik ki,
burada ... m+n-1-dən yüksək gücə malik x terminlərini ehtiva edir. Bundan, f(x) p(x)/q(x) ilə təqribən hesablana bilər.
Fon Tərifləri
Bir n dərəcəli p(x) polinomu p_0 + p_1x + p_2x^2 + ... + p_nx^n kimi yazıla bilər, burada p_i bu məsələdə tam ədədlərdir.
f(x)-in 0 ətrafında güc sırası genişlənməsi f_0 +f_1x+f_2x^2+... kimi yazıla bilər, burada f_i bu məsələdə tam ədədlərdir.
Giriş verilənləri
Giriş bir neçə haldan ibarət olacaq. Hər bir hal bir sətirdə veriləcək, m n f_0 f_1 ... f_{m+n-1} formasında, burada f_{i } f-in güc sırası genişlənməsində x_i əmsalıdır. Siz qəbul edə bilərsiniz ki, 1 ≤ m, 1 ≤ n ≤ 4, 2 ≤ m+n ≤ 10, və f_{i } tam ədədlərdir ki, |f_i| ≤ 5. Girişin sonu m = n = 0 və f üçün heç bir əmsal olmayan bir sətirlə göstəriləcək. Siz qəbul edə bilərsiniz ki, verilmiş giriş üçün unikal həll var.
Çıxış verilənləri
Hər bir test halı üçün iki sətir çıxış verin. Birinci sətirdə p(x) polinomunu, sonra isə ikinci sətirdə q(x) polinomunu çap edin. p(x) polinomu i üzrə artan qaydada düzülmüş (p_i, i) cütləri siyahısı kimi çap edilməlidir, belə ki, p_i x_i termini üçün sıfırdan fərqli əmsaldır. Hər bir sıfırdan fərqli p_i əmsalı a/b kimi çap edilməlidir, burada b > 0 və a/b ən aşağı formada ifadə edilmiş əmsaldır. Əlavə olaraq, əgər b = 1 isə yalnız a çap edin (və b-ni buraxın). Əgər p(x) = 0 isə yalnız (0, 0) olan bir sətir çap edin. Siyahıdakı cütləri bir boşluqla ayırın. q(x) polinomu eyni qaydada çap edilməlidir. Hallar arasında bir boş sətir daxil edin.