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 triunghi4.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 triunghi4.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 ordinea de la stânga la dreapta numerele scrise pe linia 1 a triunghiului.

Restricţii

• 1 <= n <= 1000
• 1 <= pi <= n+1-i, pentru 1≤i≤n
• Toate numerele din triunghi sunt numere naturale cu cel mult 18 cifre.

Exemple

triunghi4.in	triunghi4.out	Explicaţii
5 4 4 2 5 3 13 2 25 1 45	1 2 3 4 2	Triunghiul este: 45 20 25 8 12 13 3 5 7 6 1 2 3 4 2

autor: Prof. Nistor-Eugen Moţ

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com