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

• Tổng phần trên phải và phần dưới trái (được chia bởi đường chéo chính).
• Tổng phần trên trái và phần dưới phải (được chia bới đường chéo phụ).

Biết rằng tổng của các phần có bao gồm các số nằm trên các đường chéo tương ứng.

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

• In ra tổng phần trên trái, trên phải, dưới trái, dưới phải trên lần lượt trên cùng một dòng, các số cách nhau một khoảng trắng.

Sample Test

Input:

3
1 2 3
2 1 1
1 4 5

Output:

10 13 14 15

Note: