Your task is to write a program that reads a sequence of square matrices of integers, and for each one prints the sum of the numbers which are in their two diagonals.

Usign the definition

typedef vector<vector<int> > Matrix;

your program must implement and use the function

int sum_diagonals(const Matrix& mat);

that returns the sum of the numbers in the diagonals of the square matrix and non empty |mat|.

Input

The input consists of a sequence of cases. Each case starts with the size n ≥ 1 of the matrix, followed by n lines, each one with the n integers of the corresponding row.

Output

For each matrix, print a line with the sum of the numbers which are in its diagonals.

Public test cases

**Input**

1 7 2 1 2 3 4 3 1 3 0 5 2 7 -8 -4 -9 4 1000000 3 4 -1000000 1 -1000000 1000000 7 2 -1000000 1000000 8 1000000 5 6 -1000000

**Output**

7 10 -14 0

**Input**

5 11 22 33 46 15 41 33 94 58 71 56 23 45 98 21 54 15 37 26 17 65 88 99 66 11

**Output**

279

Information

- Author
- Professorat de P1
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++