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.OutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskC {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n =in.nextInt();
        long diagUL[][] = new long[n][n];
        long diagUR[][] = new long[n][n];
        long diagDR[][] = new long[n][n];
        long diagDL[][] = new long[n][n];
        int board[][] = new int[n][n];

        //UL
        for(int i=0;i<n;i++ ) {
            for(int j=0;j<n;j++){
                board[i][j]  =in.nextInt();
                if(i-1<0 || j-1<0) {
                    diagUL[i][j]= board[i][j];
                }
                else {
                    diagUL[i][j] = board[i][j] + diagUL[i-1][j-1];
                }
            }
        }

        // UR

        for(int i=0;i<n;i++ ) {
            for(int j=n-1;j>=0;j--){
                if(i-1<0 || j+1>=n) {
                    diagUR[i][j]= board[i][j];
                }
                else {
                    diagUR[i][j] = board[i][j] + diagUR[i-1][j+1];
                }
            }
        }


        // DR

        for(int i=n-1;i>=0;i-- ) {
            for(int j=n-1;j>=0;j--){
                if(i+1>=n || j+1>=n) {
                    diagDR[i][j]= board[i][j];
                }
                else {
                    diagDR[i][j] = board[i][j] + diagDR[i+1][j+1];
                }
            }
        }

        // DL


        for(int i=n-1;i>=0;i-- ) {
            for(int j=n-1;j>=0;j--){
                if(i+1>=n || j-1<0) {
                    diagDL[i][j]= board[i][j];
                }
                else {
                    diagDL[i][j] = board[i][j] + diagDL[i+1][j-1];
                }
            }
        }

        long maxS1 = Long.MIN_VALUE;
        long maxS2 = Long.MIN_VALUE;
        int x1=0,y1=0,x2=0,y2=0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if((i+j)%2==0) {
                    if(diagDL[i][j]+diagDR[i][j]+diagUL[i][j]+diagUR[i][j]-3*(long)board[i][j]>maxS1) {
                        maxS1 = diagDL[i][j]+diagDR[i][j]+diagUL[i][j]+diagUR[i][j]-3*(long)board[i][j];
                        x1=i+1;
                        y1=j+1;
                    }
                }  else {
                    if(diagDL[i][j]+diagDR[i][j]+diagUL[i][j]+diagUR[i][j]-3*(long)board[i][j]>maxS2) {
                        maxS2 = diagDL[i][j]+diagDR[i][j]+diagUL[i][j]+diagUR[i][j]-3*(long)board[i][j];
                        x2=i+1;
                        y2=j+1;
                    }
                }

            }
        }

        out.println(maxS1+maxS2);
        out.println(x1 + " "+y1 + " "+x2 + " "+y2);
    }
}

class InputReader {

    private InputStream stream;
    int curCharIndex = 0;
    int charsInBuf = 0;
     byte buf[] = new byte[16*1024];

    public InputReader(InputStream stream) {
        this.stream = stream;
    }


    public int readChar() {

        if (curCharIndex >= charsInBuf) {
            curCharIndex = 0;
            try {
                charsInBuf = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (charsInBuf <= 0)
                return -1;
        }
        return buf[curCharIndex++];
    }


    public int nextInt() {

        int c;
        do {
            c = readChar();
        }while(isWhitespace(c));

        int sign = 1;
        if (c == '-') {
            c = readChar();
            sign = -1;

        }
        int res = 0;
        do {
            res *= 10;
            res += c - '0';
            c = readChar();
        } while (!isWhitespace(c) && c!=-1);
        return sign * res;
    }


    /*
    * For the purpose of compatibilty with Chelper Chrome extension
     */


    private boolean isWhitespace(int c) {
        return  c==' ' || c=='\n'|| c=='\r' || c=='\t';
    }
}