Bessie có một dãy \(a_1, a_2, \dots, a_N\), trong đó \(1 \le N \le 300\) và \(0 \le a_i \le 10^9\) với mọi \(i\). Cô nàng sẽ không nói thẳng cho bạn dãy \(a\) mà lại thích vòng vo Tam Quốc, chỉ nói cho bạn khoảng xác định của dãy. Nghĩa là, với mỗi cặp chỉ số \(i \le j\), Bessie sẽ nói cho bạn \(r_{i, j} = \max a[i \dots j] - \min a[i \dots j]\). Cho các giá trị của \(r\), hãy xây dựng lại một dãy mà có thể là dãy ban đầu của Bessie. Các giá trị trong dãy phải nằm trong đoạn \([-10^9, 10^9]\).

Input

• Dòng đầu tiên là số \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) là các số \(r_{i, i}, r_{i, i + 1}, \dots r_{i, n}\).
• Dữ liệu đảm bảo luôn có dãy \(a\) với các giá trị nằm trong đoạn \([0, 10^9]\) thoả mãn điều kiện của test.

Output

• In ra một dòng là \(N\) số nguyên \(b_1, b_2, \dots, b_N \in [-10^9, 10^9]\) thoả mãn \(r_{i, j} = \max a[i \dots j] - \min a[i \dots j] \forall i \le j\).

Scoring

• Subtask \(1\): \(r_{1, N} \le 1\).
• Subtask \(2\): \(r_{i, i + 1} = 1 \forall 1 \le i \le N\).
• Subtask \(3\): Không có ràng buộc thêm.

3
0 2 2
0 1
0

1 3 2

3
0 1 1
0 0
0

0 1 1

4
0 1 2 2
0 1 1
0 1
0

1 2 3 2

4
0 1 1 2
0 0 2
0 2
0

1 2 2 0