Input

Dòng đầu gồm số n (1 ≤ n ≤ 1000)

Dòng thứ i (1 ≤ i ≤ n) trong n dòng sau chứa n số nguyên ~a_i, 1, a_i, 2, ..., a_i, n (a_i, j ≤ 10^9)~

Output

Gồm một dòng chứa 2 số nguyên lần lượt là tổng đường chéo chính và tổng đường chéo phụ

Example

Sample Input

4
1 2 3 4
5 6 7 8
9 1 1 2
3 4 5 6

Sample Output

14 15