Xây Dựng Lại Range

Bessie có một mảng nhưng không muốn tiết lộ trực tiếp. Thay vào đó, cô ấy cung cấp range (hiệu giữa giá trị lớn nhất và nhỏ nhất) của mọi mảng con liên tiếp. Cho các giá trị range này, hãy xây dựng lại một mảng thỏa mãn.

Dữ liệu vào

• Dòng 1: số nguyên $N$ ($1\le N\le 300$).
• $N$ dòng tiếp theo: dòng thứ $i$ chứa $N-i+1$ số nguyên $r_{i,i},r_{i,i+1},\dots ,r_{i,N}$ là range của mảng con từ vị trí $i$ đến $j$.

Dữ liệu ra

In ra $N$ số nguyên $b_1,b_2,\dots ,b_N$ ($-{10}^9\le b_i\le {10}^9$) sao cho với mọi $i\le j$, range của $b_i,\dots ,b_j$ bằng $r_{i,j}$.

Ràng buộc

• $1\le N\le 300$
• Các giá trị trong mảng nằm trong $[-{10}^9,{10}^9]$
• Luôn tồn tại lời giải

Ví dụ