Cho một bảng ~A~ kích thước ~n \times n~ gồm các số nguyên dương. Hãy đưa ra:

• Tổng các số thuộc đường chéo chính.
• Tổng các số nằm ở phía trên đường chéo chính.

Input

• Dòng đầu tiên chứa số ~n~.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số mô tả bảng ~A~.

Các số được nhập vào là các số nguyên dương không vượt quá ~1000~.

Output

• Dòng thứ nhất in ra tổng các số thuộc đường chéo chính của bảng ~A~.
• Dòng thứ hai in ra tổng các số phía trên đường chéo chính của bảng ~A~.

Sample Test

Input:

3
2 1 3
1 9 5
1 1 1

Output:

12
9

Note:

• Các số ở thuộc đường chéo chính là:

2
  9
    1

• Các số ở phía trên đường chéo chính là:

  1 3
    5