triunghi

Se consideră un triunghi alcătuit din numere naturale scrise pe $n$ linii ca în figura alăturată. Liniile triunghiului sunt numerotate de la $1$ la $n$, începând cu linia de la baza triunghiului (linia de jos), iar poziţiile pe linie sunt numerotate începând cu $1$ de la stânga la dreapta.
Fiecare număr din triunghi, exceptând pe cele de pe linia $1$, este egal cu suma numerelor aflate imediat sub el, în stânga şi respectiv în dreapta lui.

Cerință

Cunoscând câte un număr de pe fiecare linie a triunghiului, determinaţi toate numerele de pe linia $1$.

Date de intrare

Fișierul de intrare triunghi.in conține pe prima linie numărul natural $n$ reprezentând numărul de linii din triunghi. Pe următoarele $n$ linii sunt descrise informaţiile despre triunghi. Mai exact, pe linia $i$ dintre cele $n$ se află două numere naturale separate prin spaţiu $p_i \ v_i$ indicând poziţia şi respectiv valoarea numărului cunoscut de pe linia $i$ a triunghiului.

Date de ieșire

Fișierul de ieșire triunghi.out va conține o singură linie, pe care se găsesc $n$ numere naturale separate prin câte un spaţiu, reprezentând în ordine de la stânga la dreapta numerele scrise pe linia $1$ a triunghiului.

Restricții și precizări

• $1 \leq n \leq 1 \ 000$;
• $1 \leq p_i \leq n+1-i$;
• Toate numerele din triunghi sunt numere naturale cu cel mult $18$ cifre.

Exemplu

triunghi.in

5
4 4
2 5
3 13
2 25
1 45

triunghi.out

1 2 3 4 2

Explicație

Triunghiul este:

      45
    20  25
   8  12 13
  3  5  7  6
 1  2  3  4  2