Zaharel si Bronzarel joaca urmatorul joc: se pun pe masa N gramezi de monede. Se stie ca daca Zaharel ia gramada i primeste A_i din monedele din gramada, iar daca Bronzarel ia gramada i primeste B_i din monedele din gramada (se stie ca fiecare gramada are cel putin max(A_i, B_i) monede iar monedele care raman se arunca). Cei doi jucatori iau alternativ cate o gramada, pana cand se epuizeaza toate cele N, iar Zaharel este primul care ia o gramada. La final, castiga jucatorul cu mai multe monede. In cazul in care cantitatile de monede sunt egale, jocul se considera remiza.

Cerinta

Stiind ca Zaharel si Bronzarel joaca optim, determinati numarul de monede pe care il va avea fiecare jucator la final. Prin joc optim se intelege ca fiecare jucator incearca sa mareasca diferenta dintre numarul de monezi pe care le detine si numarul de monezi ale celuilalt jucator, iar in cazul in care are mai multe posiblitati de a obtine aceeasi diferenta va incerca sa-si mareasca numarul de monede.

Date de intrare

Pe prima linie a fisierului de intrare gramezi.in este scris numarul natural N. Pe urmatoarele N linii se vor gasi cate doua numere naturale separate prin cate un spatiu, reprezentand valorile A_i, respectiv B_i.

Date de iesire

Prima linie a fisierului gramezi.out va contine doua numere naturale separate prin spatiu reprezentand scorul lui Zaharel, respectiv scorul lui Bronzarel.

Restrictii

1 <= N <= 30 000
1 <= A_i, B_i <= 30 000

Exemple

Mircea Paşoi
Universitatea Bucuresti,Facultatea de Matematica si Informatica
bogdanpasoi@yahoo.com