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.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;

/**
 * Created by jizhe on 2016/1/14.
 */
public class GargariAndBishops {
    //tricky. almost diagonal by myself. checking method inspired. point1 and point2 belongs to 2 different groups of points.
    public static class FasterScanner {
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = System.in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

        public long[] nextLongArray(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }

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

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }

    public static void main(String[] args) {
        //Scanner in = new Scanner(new BufferedInputStream(System.in));
        FasterScanner in = new FasterScanner();

        int N = in.nextInt();
        long[][] a = new long[N][N];
        long[] diagnal1 = new long[2*N-1];
        long[] diagnal2 = new long[2*N-1];
        for( int i = 0; i < N; i++ )
        {
            for( int j = 0; j < N; j++ )
            {
                long number = in.nextLong();
                a[i][j] = number;
                diagnal1[i+N-1-j] += number;
                diagnal2[i+j] += number;
            }
        }

        /*System.out.printf("1st digonal:\n");
        for( int i = 0; i < 2*N-1; i++ )
        {
            System.out.printf("digonal1[%d]: %d\n", i, diagnal1[i]);
        }
        System.out.printf("2nd digonal:\n");
        for( int i = 0; i < 2*N-1; i++ )
        {
            System.out.printf("digonal2[%d]: %d\n", i, diagnal2[i]);
        }*/

        long max1 = Long.MIN_VALUE, max2 = Long.MIN_VALUE;
        int row1 = -1, row2 = -1, col1 = -1, col2 = -1;
        for( int i = 0; i < N; i++ )
        {
            for( int j = i&1; j < N; j +=2 )
            {
                //System.out.printf("Checking max1, j: %d\n", j);
                if( diagnal1[i+N-1-j]+diagnal2[i+j]-a[i][j] > max1 )
                {
                    max1 = diagnal1[i+N-1-j]+diagnal2[i+j]-a[i][j];
                    row1 = i;
                    col1 = j;
                    //System.out.printf("(%d, %d) is max1: %d\n", i+1, j+1, max1);
                }
            }

            for( int j = ((i&1)^1); j < N; j +=2 )
            {
                //System.out.printf("Checking max2, j: %d\n", j);
                if( diagnal1[i+N-1-j]+diagnal2[i+j]-a[i][j] > max2 )
                {
                    max2 = diagnal1[i+N-1-j]+diagnal2[i+j]-a[i][j];
                    row2 = i;
                    col2 = j;
                    //System.out.printf("(%d, %d) is max2: %d\n", i+1, j+1, max2);
                }
            }
        }

        System.out.printf("%d\n%d %d %d %d\n", max1+max2, row1+1, col1+1, row2+1, col2+1);
    }
}
