Bessie has an array a1,…,aN, where 1≤N≤300 and 0≤ai≤109 for all i. She won't tell you a itself, but she will tell you the range of each subarray of a. That is, for each pair of indices i≤j, Bessie tells you ri,j=maxa[i…j]−mina[i…j]. Given these values of r, please construct an array that could have been Bessie's original array. The values in your array should be in the range [−109,109].
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
Another N lines follow. The ith of these lines contains the integers ri,i,ri,i+1,…,ri,N.
It is guaranteed that there is some array a with values in the range [0,109] such that for all i≤j, ri,j=maxa[i…j]−mina[i…j].
OUTPUT FORMAT (print output to the terminal / stdout):
Output one line containing N integers b1,b2,…,bN in the range [−109,109] representing your array. They must satisfy ri,j=maxb[i…j]−minb[i…j] for all i≤j.
SAMPLE INPUT:
3
0 2 2
0 1
0
SAMPLE OUTPUT:
1 3 2
For example, r1,3=maxa[1…3]−mina[1…3]=3−1=2.
SAMPLE INPUT:
3
0 1 1
0 0
0
SAMPLE OUTPUT:
0 1 1
This example satisfies the constraints for subtask 1.
SAMPLE INPUT:
4
0 1 2 2
0 1 1
0 1
0
SAMPLE OUTPUT:
1 2 3 2
This example satisfies the constraints for subtask 2.
SAMPLE INPUT:
4
0 1 1 2
0 0 2
0 2
0
SAMPLE OUTPUT:
1 2 2 0
SCORING:
Test 5 satisfies r1,N≤1.
Tests 6-8 satisfy ri,i+1=1 for all 1≤i<N.
Tests 9-14 satisfy no additional constraints.
Problem credits: Danny Mittal