მოცემულია n წვეროიანი მიუმართავი ხე. i-ურ წვეროს მინიჭებული აქვს ნატურალური რიცხვი x_i. ნებისმიერ ორ L და R წვეროს შორის მანძილი გამოითვლება შემდეგნაირად:

(L-დან R-მდე გზაზე არსებული x_i-ების ნამრავლი) / (L-დან R-მდე გზაზე არსებული  წვეროების რაოდენობა)

თქვენი მიზანია, იპოვოთ უმოკლესი შესაძლო გზის სიგრძე და გამოიტანოთ უკვეცი წილადის სახით.

შემომავალი მონაცემები: პირველ სტრიქონზე შემოდის ერთი რიცხვი n (1≤n≤10⁶). შემდეგ  n-1 სტრიქონზე შემოდის ორ-ორი რიცხვი A_i და B_i (1≤A_i,B_i≤n) - წიბოების აღწერა. ბოლო n სტრიქონზე კი შემოდის x_i (1≤x_i≤10⁹)-ები. 

გამომავალი მონაცემები: გამომავალი მონაცემების ერთადერთ ხაზზე უნდა გამოიტანოთ ამოცანის პასუხი ფორმატით P/Q (სადაც P და Q თანამარტივი რიცხვებია).

მაგალითები

შესატანი მონაცემები
2
1 2
3
4

                  დაკოპირება

გამოსატანი მონაცემები
3/1
                  დაკოპირება

შესატანი მონაცემები
5
1 2
2 4
1 3
5 2
2
1
1
1
3

                  დაკოპირება

გამოსატანი მონაცემები
1/2
                  დაკოპირება