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
def main():
    n = int(raw_input())
    l = list(tuple(map(int, raw_input().split())) for _ in xrange(n))
    aa, bb = [], []
    for i in xrange(n):
        aa.append(sum(l[i - j][j] for j in xrange(i + 1)))
    for i in xrange(n, 2 * n - 1):
        aa.append(sum(l[i - j][j] for j in xrange(i - n + 1, n)))
    for i in xrange(0, -n, -1):
        bb.append(sum(l[j - i][j] for j in xrange(n + i)))
    for i in xrange(n - 1, 0, -1):
        bb.append(sum(l[j - i][j] for j in xrange(i, n)))
    x1 = y1 = t1 = x2 = y2 = t2 = -1
    for x, row in enumerate(l):
        for y, z in enumerate(row):
            t = aa[x + y] + bb[x - y] - z
            if (x ^ y) & 1:
                if t1 < t:
                    t1, x1, y1 = t, x, y
            else:
                if t2 < t:
                    t2, x2, y2 = t, x, y
    print t1 + t2
    print x1 + 1, y1 + 1, x2 + 1, y2 + 1


if __name__ == '__main__':
    main()
