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()))

mat=[]
for _ in range(int(input())):
    mat.append(I())
n=len(mat)
def sumDiag(mat):
    diag_sum=[]
    diag_sum2=[]
    n=len(mat)
    for i in range(n):
        s=0
        for j in range(0,n-i):
            s+=mat[j][(j+i)]
        diag_sum.append(s)
        if i!=0:
            s=0
            for j in range(0,n-i):
                s+=mat[j+i][(j)]
            diag_sum2.append(s)
    return diag_sum2[::-1]+diag_sum

def antiDiag(mat):
    def mirror(mat):
        for i in range(len(mat)):
            for j in range(len(mat[0])//2):
                t=mat[i][j]
                mat[i][j]=mat[i][len(mat[0])-1-j]
                mat[i][len(mat[0])-1-j]=t
        return mat
    mat=mirror(mat)
    out=sumDiag(mat)
    mirror(mat)
    return out[::-1]

d1=sumDiag(mat)
d2=antiDiag(mat)
def ret(i,j):
    return d1[n-1-(i-j)]+d2[i+j]-mat[i][j]

m1=0
m2=0
best1=(1,1)
best2=(1,2)
for i in range(n):
    for j in range(n):
        if (i+j)%2==0 and m1<ret(i,j):
            m1=ret(i,j)
            best1=(i+1,j+1)
        elif (i+j)%2==1 and m2<ret(i,j):
            m2=ret(i,j)
            best2=(i+1,j+1)

print(m1+m2)
print(" ".join(map(str,[best1[0],best1[1],best2[0],best2[1]])))