矩阵对角求和

求一个n×n矩阵对角线元素之和,其中1≤n<100,矩阵元素都小于10000。

Input

第一行是一个正整数n。

然后是n行,每行对应矩阵的每行,元素间用空格隔开。

Output

第一行为主对角线元素和,第二行为副对角线的元素和。

Examples

Input

3
5724 1478 9358
6962 4464 5705
8145 3281 6827

Output

17015
21967

来源

数据结构高分笔记
Time limit 1 second
Memory limit 32 MB
讨论 统计