Gargari is jealous that his friend Caisa won the game from the previous problem. He wants to prove that he is a genius.

He has a n × n chessboard. Each cell of the chessboard has a number written on it. Gargari wants to place two bishops on the chessboard in such a way that there is no cell that is attacked by both of them. Consider a cell with number x written on it, if this cell is attacked by one of the bishops Gargari will get x dollars for it. Tell Gargari, how to place bishops on the chessboard to get maximum amount of money.

We assume a cell is attacked by a bishop, if the cell is located on the same diagonal with the bishop (the cell, where the bishop is, also considered attacked by it).

Input

The first line contains a single integer n (2 ≤ n ≤ 2000). Each of the next n lines contains n integers aij (0 ≤ aij ≤ 109) — description of the chessboard.

Output

On the first line print the maximal number of dollars Gargari will get. On the next line print four integers: x1, y1, x2, y2 (1 ≤ x1, y1, x2, y2 ≤ n), where xi is the number of the row where the i-th bishop should be placed, yi is the number of the column where the i-th bishop should be placed. Consider rows are numbered from 1 to n from top to bottom, and columns are numbered from 1 to n from left to right.

If there are several optimal solutions, you can print any of them.

Examples

Input

4
1 1 1 1
2 1 1 0
1 1 1 0
1 0 0 1


Output

12
2 2 3 2

from sys import stdin
input = stdin.buffer.readline
I = lambda : list(map(int,input().split()))
n = int(input())
ans = []

for _ in range(n):
    arr = I()
    ans.append(arr)

topLeft, bottomLeft = {}, {}

for i in range(n):
    for j in range(n):
        topLeft[i-j] = topLeft.get(i-j, 0) + ans[i][j]
        bottomLeft[i+j] = bottomLeft.get(i+j, 0) + ans[i][j]

mx1, mx2, pos1, pos2 = -1, -1, [-1,-1], [-1,-1]

for i in range(n):
    for j in range(n):
        if (i+j) & 1:
            if mx1 < topLeft[i-j] + bottomLeft[i+j] - ans[i][j]:
                mx1, pos1 = topLeft[i-j] + bottomLeft[i+j] - ans[i][j], [i+1,j+1]
        else:
            if mx2 < topLeft[i - j] + bottomLeft[i + j] - ans[i][j]:
                mx2, pos2 = topLeft[i - j] + bottomLeft[i + j] - ans[i][j], [i+1, j+1]

print(mx1+mx2)
print(pos1[0], pos1[1], pos2[0], pos2[1])