Temă

^& missed opportunity...

Cerință

Într-o zi fantastică de joi, te pui la birou și decizi să îți faci tema la materia ta preferată, matematica. Deschizi caietul și observi că profesoara ți-a dat un singur exercițiu de făcut (în mod normal, primești minimum 2 pagini din culegere și 3 din manual). Uimit, deschizi culegerea și observi un șir lung de fracții. Acesta nu e doar pe o pagină, nici pe două, ci pe 39 de pagini. După un proces de numărat foarte amplu, ai observat că șirul este alcătuit din exact $N$ fracții, iar cerința exercițiului este să calculezi suma tuturor fracțiilor și să o scrii simplificată. Din cauza lungimii imense a exercițiului, te-ai decis să scrii un program care să iți rezolve tema!

Date de intrare

Pe prima linie a fișierului de intrare tema.in se găsește un număr întreg $N$, reprezentând numărul de fracții din temă.
Pe fiecare dintre următoarele $N$ linii, se află câte 2 numere, $A_i$ și $B_i$, reprezentând numărătorul, respectiv numitorul fracției $\frac{A_i}{B_i}$ din temă.

Date de ieșire

Pe prima linie a fișierului de ieșire tema.out se vor găsi $2$ numere întregi, $X$ și $Y$, separate printr-un spațiu, reprezentând suma celor $N$ fracții sub forma fracției $\frac{X}{Y}$ simplificate.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• $1 \leq A_i, B_i \leq 10^9$, pentru $1 \leq i \leq N$;
• $1 \leq X, Y \leq 10^{18}$;
• O fracție $\frac{X}{Y}$ este simplificată dacă $cmmdc(X, Y) = 1$;
• Numitorul $Y$ trebuie afișat chiar dacă $Y = 1$;

  #	Punctaj	Restricții
  1	37	$1 \leq N \leq 10$ și $1 \leq A_i, B_i \leq 15, 1 \leq i \leq N$
  2	31	$1 \leq N \leq 10000$ și $1 \leq A_i, B_i \leq 10^7, 1 \leq i \leq N$
  2	32	Fără restricții suplimentare

Exemplul 1

tema.in

2
1 2
1 4

tema.out

3 4

Explicație

Cele 2 fracții sunt $\frac{1}{2}$ și $\frac{1}{4}$, iar suma lor este $\frac{3}{4}$, fracție care este deja simplificată.

Exemplul 2

tema.in

3
1 3
3 9
16 12

tema.out

2 1

Explicație

Cele 3 fracții sunt $\frac{1}{3}$, $\frac{3}{9}$ și $\frac{16}{12}$. Suma lor este $\frac{72}{36}$, care poate fi scrisă simplificată ca $\frac{2}{1}$.