Cho ma trận vuông cỡ \(n\). Tính các tổng của các số trên đường chéo song song với đường chéo chính của ma trận đã cho.

Ghi chú: Đường chéo chính của ma trận vuông nối góc trên bên trái với góc dưới bên phải.

Đầu vào

Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 1000)\), cỡ của ma trận vuông.

\(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên trong khoảng \([10^9, -10^9]\), các phần tử của ma trận.

Đầu ra

\(n\) dòng, mỗi dòng là tổng các số trên một đường chéo.

Các đường chéo được tính và in ra từ trên xuống dưới.

Ví dụ

Đầu vào:

4 
1 2 4 8
2 4 8 16
4 8 16 32
1024 16 32 64

Đầu ra:

8
20
42
85
42 
20
1024

Giải thích:

\(a_{03} = 8\)

\(a_{02} + a_{13} = 4 + 16 = 20\)

\(a_{01} + a_{12} + a_{23} = 2 + 8 + 32 = 42\)

\(a_{00} + a_{11} + a_{22} + a_{33} = 1 + 4 + 16 + 64 = 85\)

\(...\)