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

import java.io.*;

/**
 * Created by Rafatdin on 04.03.15.
 */

public class c463 {
    static StreamTokenizer in;
    static PrintWriter out;

    static int next() throws IOException
    {
        in.nextToken();
        return (int)in.nval;
    }
    static int indicesMatrix [][] = new int [2][2];
    static long highestVal[] = new long[2];
    static void Update(int oddEven, int i, int j, long val){
        if(val > highestVal[oddEven]){
            highestVal[oddEven] = val;
            indicesMatrix[oddEven][0] = i;
            indicesMatrix[oddEven][1] = j;
        }
    }
    public static void main(String[] args)throws IOException {
        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));


        int n = next();
        long d1[] = new long[2*(n+1)], d2[] = new long [2*(n+1)];
        int[][] a = new int [n+1][n+1];


        highestVal[0] = -1;
        highestVal[1] = -1;
        for(int i = 1;i <= n; ++i){
            for(int j = 1;j <= n; ++j){
                a[i][j] = next();
                d1[i+j] += a[i][j];
                d2[i-j+n] += a[i][j];
            }
        }

        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                Update((i+j)&1, i, j, d1[i+j]+d2[i-j+n]-a[i][j]);
            }
        }

        out.println(highestVal[0]+highestVal[1]);
        out.print(indicesMatrix[0][0]+" "+indicesMatrix[0][1]+" "+indicesMatrix[1][0]+" "+indicesMatrix[1][1]);
        out.flush();
    }
}
