Trên bảng có \(N\) số nguyên được viết từ trái sang phải. Số nguyên thứ \(i\) từ trái sang là \(A_i\) (\(1 \le i \le N\)).

Ta lặp lại thao tác sau:

Gọi \(k\) là độ dài của dãy số ở hàng dưới cùng hiện tại. Dựa trên dãy số này, viết thêm ngay bên dưới một dãy mới có độ dài \(k - 1\). Với mỗi \(i\) từ \(1\) đến \(k - 1\), số thứ \(i\) của dãy mới bằng tổng của số thứ \(i\) và số thứ \(i + 1\) trong dãy ở hàng ngay phía trên.

Hãy tìm tất cả các dãy số được viết thêm sau khi thực hiện \(N - 1\) thao tác.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\), cách nhau bởi dấu cách.

Dữ liệu ra

In ra \(N - 1\) dòng. Dòng thứ \(i\) (\(1 \le i \le N - 1\)) chứa dãy số được viết thêm ở thao tác thứ \(i\), theo thứ tự từ trái sang phải, các số cách nhau bởi dấu cách.

Chỉ in ra đáp án, không in thêm bất kỳ nội dung nào khác, kể cả lời nhắc nhập dữ liệu.

Ràng buộc

• \(2 \le N \le 10\).
• \(1 \le A_i \le 10\) với mọi \(1 \le i \le N\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Ví dụ

5
1 3 5 7 9

4 8 12 16
12 20 28
32 48
80

7
1 2 3 4 3 2 1

3 5 7 7 5 3
8 12 14 12 8
20 26 26 20
46 52 46
98 98
196

10
1 9 2 4 4 9 2 3 5 6

10 11 6 8 13 11 5 8 11
21 17 14 21 24 16 13 19
38 31 35 45 40 29 32
69 66 80 85 69 61
135 146 165 154 130
281 311 319 284
592 630 603
1222 1233
2455

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.