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 triunghi3.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 (1≤i≤n) dintre cele n se află două numere naturale separate prin spaţiu pi vi 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 triunghi3.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 ≤ n ≤ 1000
• 1 ≤ pi ≤ n+1-i, pentru 1≤i≤n
• Toate numerele din triunghi sunt numere naturale cu cel mult 18 cifre.

Exemplu:

triunghi3.in

5
4 4
2 5
3 13
2 25
1 45

triunghi3.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