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 __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase
from math import inf


def main():
    # a bishop has to be on a cell intercepted by even diagonals,
    # and another on a cell intercepted by odd diagonals

    # i + j is even -> white
    # i + j is odd -> gray

    # diagonal 1 -> i - j (top-left to bottom-right) (this difference is constant)
    # diagonal 2 -> i + j (top-right to bottom-left) (this sum is constant)

    # calculate the sum of each diagonal (n2)

    # find the best cell (with max total) intercepted by even diagonals and the
    # best cell (with max total) intercepted by odd diagonals

    n = int(input())
    chessboard = [
        [ int(x) for x in input().split() ]
        for row in range(n)
    ]

    mainDiagonalSums = {}
    secondaryDiagonalSums = {}

    for i in range(n):
        for j in range(n):
            mainDiagonal = i - j
            if mainDiagonal in mainDiagonalSums:
                mainDiagonalSums[mainDiagonal] += chessboard[i][j]
            else:
                mainDiagonalSums[mainDiagonal] = chessboard[i][j]

            secondaryDiagonal = i + j
            if secondaryDiagonal in secondaryDiagonalSums:
                secondaryDiagonalSums[secondaryDiagonal] += chessboard[i][j]
            else:
                secondaryDiagonalSums[secondaryDiagonal] = chessboard[i][j]

    maxPoints = [-inf, -inf]
    bestPosition = [None, None]

    for i in range(n):
        for j in range(n):
            points = (
                mainDiagonalSums[i-j] + secondaryDiagonalSums[i+j]
                - chessboard[i][j]
            )

            if (i + j) & 1:
                if points > maxPoints[1]:
                    bestPosition[1] = (i, j)
                    maxPoints[1] = points
            else:
                if points > maxPoints[0]:
                    bestPosition[0] = (i, j)
                    maxPoints[0] = points

    print(sum(maxPoints))
    print(' '.join([ f'{i+1} {j+1}' for i, j in bestPosition ]))


BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

input = lambda: sys.stdin.readline().rstrip("\r\n")

def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep = kwargs.pop("sep", " ")
    file = kwargs.pop("file", sys.stdout)

    atStart = True
    for x in args:
        if not atStart:
            file.write(sep)
        file.write(str(x))
        atStart = False
    file.write(kwargs.pop("end", "\n"))

    if kwargs.pop("flush", False):
        file.flush()

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

main()
