Đề bài

Ta xem xét một bảng số vuông, gọi nó là ma trận vuông cỡ \(n \times n\). Xét các hình vuông đồng tâm có tâm là tâm của bảng số ban đầu. Hãy tính tổng các số ở trên các cạnh của mỗi hình vuông đó. Với \(n\) là số lẻ thì tâm của ma trận là phần tử \(a[\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 1]\), còn với \(i\) là số chẵn thì tâm được xem là giao điểm của đường chéo chính và đường chéo phụ.

• Hình vuông đồng tâm: Hình vuông nằm bên trong hình vuông khác, có cùng tâm.

Yêu cầu:

• Hãy in ra tổng các số trên cạnh của các hình vuông đồng tâm từ trong ra ngoài

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \leq n \leq 300)\).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên biểu diễn các phần tử của ma trận. Các số nguyên này đều có giá trị tuyệt đối nhỏ hơn \(10^6\).

Dữ liệu ra

• Một dòng gồm các số, trong đó số thứ \(i\) là tổng các phần tử nằm trên cạnh của hình vuông thứ \(i\) (từ hình vuông nhỏ nhất có kích thước nhỏ nhất cho đến hình vuông lớn nhất \(n \times n\)).

Giới hạn

• \(1 \leq n \leq 300\)
• \(|a_{ij}| \leq 10^6\)

Sample Input

4
1 2 3 1
4 5 6 1
1 2 3 1
1 1 1 1

Sample Output

16 18

Giải thích

• Ma trận đã cho: \(M = \begin{bmatrix} 1 & 2 & 3 & 1 \\ 4 & 5 & 6 & 1 \\ 1 & 8 & 3 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix}\)

• Hình vuông \(M_2\) (kích thước \(2 \times 2\)): Tâm của ma trận là \(4\) phần tử ở giữa có tổng là \(16\).

• Hình vuông \(M_4\) (kích thước \(4 \times 4\)): Tổng các phần tử trên cạnh bao gồm:

• Dòng trên cùng: \(1 + 2 + 3 + 1\)
• Dòng dưới cùng: \(1 + 1 + 1 + 1\)
• Cột trái và phải (không trùng góc): \(4 + 1 + 1 + 1\)
• Tổng: \(18\).