Cho một bảng kích thước ~N \times N~, mỗi ô của bảng chứa một số nguyên. Thực hiện một đường cắt ngang và một đường cắt dọc chia bảng thành bốn phần là các hình chữ nhật hoặc hình vuông. Với mỗi cách cắt, giá trị của mỗi phần là tổng các số nguyên trong phần đó.

Yêu cầu: Hãy xác định chênh lệch nhỏ nhất giữa phần có giá trị lớn nhất và phần có giá trị nhỏ nhất.

Input

Dữ liệu vào từ tệp văn bản B2CL.INP gồm:

• Dòng thứ nhất chứa số nguyên dương ~N~ ~(2 \le N \le 10^3)~;
• ~N~ dòng tiếp theo, mỗi dòng gồm ~N~ số nguyên có giá trị tuyệt đối không quá ~10^9~. Các số trên cùng một dòng cách nhau ít nhất một khoảng trắng.

Output

Đưa ra tệp văn bản B2CL.OUT một số nguyên duy nhất là kết quả cần tìm.

Ví dụ

Ví dụ 1

Input

2
1 2
3 4

Output

3

Giải thích: Có 1 cách cắt:

1 | 2
--+--
3 | 4

Nhỏ nhất: ~1~, Lớn nhất: ~4~, Chênh lệch: ~3~.

Chênh lệch nhỏ nhất giữa phần có giá trị lớn nhất và phần có giá trị nhỏ nhất: 3.

Ví dụ 2

Input

3
1 2 2
1 -1 4
2 2 -5

Output

4

Giải thích: Có 4 cách cắt:

Cách cắt 1 (cắt ngang giữa dòng 1 và dòng 2, cắt dọc giữa cột 1 và cột 2):

 1 |  2  2
---+------
 1 | -1  4
 2 |  2 -5

Nhỏ nhất: ~0~, Lớn nhất: ~4~, Chênh lệch: ~4~.

Cách cắt 2 (cắt ngang giữa dòng 1 và dòng 2, cắt dọc giữa cột 2 và cột 3):

 1  2 |  2
------+---
 1 -1 |  4
 2  2 | -5

Nhỏ nhất: ~-1~, Lớn nhất: ~4~, Chênh lệch: ~5~.

Cách cắt 3 (cắt ngang giữa dòng 2 và dòng 3, cắt dọc giữa cột 1 và cột 2):

 1 |  2  2
 1 | -1  4
---+------
 2 |  2 -5

Nhỏ nhất: ~-3~, Lớn nhất: ~7~, Chênh lệch: ~10~.

Cách cắt 4 (cắt ngang giữa dòng 2 và dòng 3, cắt dọc giữa cột 2 và cột 3):

 1  2 |  2
 1 -1 |  4
------+---
 2  2 | -5

Nhỏ nhất: ~-5~, Lớn nhất: ~6~, Chênh lệch: ~11~.

Trong các cách cắt, cách cắt thứ 1 có chênh lệch nhỏ nhất giữa phần có giá trị lớn nhất và phần có giá trị nhỏ nhất là 4.

Giới hạn

• ~2 \le N \le 10^3~; mỗi số trong bảng có giá trị tuyệt đối không quá ~10^9~.
• Subtask 1: Có ít nhất 35% số test có ~N \le 3~;
• Subtask 2: Có ít nhất 14% số test có ~N = 4~;
• Subtask 3: Có ít nhất 20% số test có ~4 < N \le 10^2~;
• Subtask 4: Số test còn lại không có ràng buộc gì thêm.