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.BufferedWriter;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.InputStream;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.UnsupportedEncodingException;
import java.math.BigInteger;
//################################################################################################################
public class Main {
	class InputReader1 {
    //private final boolean finished = false;

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

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

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

    public int peek() {
        if (numChars == -1)
            return -1;
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                return -1;
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar];
    }

    public int readInt() {
        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 long readLong() {
        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 String readString() {
        int length = readInt();
        if (length < 0)
            return null;
        byte[] bytes = new byte[length];
        for (int i = 0; i < length; i++)
            bytes[i] = (byte) read();
        try {
            return new String(bytes, "UTF-8");
        } catch (UnsupportedEncodingException e) {
            return new String(bytes);
        }
    }

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

    private String readLine0() {
        StringBuffer buf = new StringBuffer();
        int c = read();
        while (c != '\n' && c != -1) {
            if (c != '\r')
                buf.appendCodePoint(c);
            c = read();
        }
        return buf.toString();
    }

    public String readLine() {
        String s = readLine0();
        while (s.trim().length() == 0)
            s = readLine0();
        return s;
    }

    public String readLine(boolean ignoreEmptyLines) {
        if (ignoreEmptyLines)
            return readLine();
        else
            return readLine0();
    }

    public BigInteger readBigInteger() {
        try {
            return new BigInteger(readString());
        } catch (NumberFormatException e) {
            throw new InputMismatchException();
        }
    }

    public char readCharacter() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    public double readDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, readInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, readInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public boolean isExhausted() {
        int value;
        while (isSpaceChar(value = peek()) && value != -1)
            read();
        return value == -1;
    }

    public String next() {
        return readString();
    }

    public boolean readBoolean() {
        return readInt() == 1;
    }
    public void close(){
        try {
            stream.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

    class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream stream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(stream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void println(String s) {
            writer.println(s);
        }
        public void println(int x) {
            writer.println(x);
        }
        public void print(int x) {
            writer.print(x);
        }
	public void println(long x) {
	    writer.println(x);
	}        
        public void printSpace() {
            writer.print(" ");
        }
        public void close() {
            writer.close();
        }
    }

    public static void main(String[] args) {
    	Main main = new Main();
        InputReader1 reader = main.new InputReader1(System.in);
        OutputWriter writer = main.new OutputWriter(System.out);
        //put your code here
        int n = reader.readInt();
        int[][] b = new int[n][n];
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                b[i][j] = reader.readInt();
            }
        }
        long[] sum1 = new long[2 * n - 1];
        traverseDiagonals(b, sum1);
        /*
         * for (int i = 0; i < sum1.length; i++) { System.out.print(sum1[i] + " "); }
         * System.out.println();
         */
        long[] sum2 = new long[2 * n - 1];
        traverseOtherDiagonals(b, sum2);
        /*
         * for (int i = 0; i < sum2.length; i++) { System.out.print(sum2[i] + " "); }
         * System.out.println();
         */
        long s1 = -1;
        int r1 = -1, c1 = -1;
        int r2 = -1, c2 = -1;
        long s2 = -1;
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                int i1 = n - (i - j) - 1;
                int i2 = i + j;
                // System.out.println("i1 : " + i1);
                // System.out.println("i2 : " + i2);
                if ((i + j) % 2 == 0) {
                    if (sum1[i1] + sum2[i2] - b[i][j] > s1) {
                        s1 = sum1[i1] + sum2[i2] - b[i][j];
                        r1 = i;
                        c1 = j;
                        // System.out.println("r1 : " + r1);
                        // System.out.println("c1 : " + c1);
                    }
                }
                if ((i + j) % 2 != 0) {
                    if (sum1[i1] + sum2[i2] - b[i][j] > s2) {
                        s2 = sum1[i1] + sum2[i2] - b[i][j];
                        r2 = i;
                        c2 = j;
                        // System.out.println("r2 : " + r2);
                        // System.out.println("c2 : " + c2);
                    }
                }
            }
        }
        writer.println(s1 + s2);
        writer.println((r1 + 1) + " " + (c1 + 1) + " " + (r2 + 1) + " " + (c2 + 1));        
        reader.close();
        writer.close();        
    }
    public static void traverseDiagonals(int[][] b, long[] sum) {
        int rows = b.length;
        int cols = b[0].length;
        if (rows != cols) {
            System.out.println("This method works only for square matrices . . .");
        }
        for (int i = 0; i < 2 * rows - 1; i++) {
            int sz = i < rows ? i + 1 : 2 * rows - i - 1;
            int r = i < rows ? rows - i - 1 : 0;
            int c = i < rows ? 0 : i + 1 - rows;
            for (int j = 0; j < sz; j++) {
                // System.out.print(b[r + j][c + j] + " ");
                sum[i] += b[r + j][c + j];
            }
            // System.out.println();
        }
    }

    public static void traverseOtherDiagonals(int[][] b, long[] sum) {
        int rows = b.length;
        int cols = b[0].length;
        if (rows != cols) {
            System.out.println("This method works only for square matrices . . .");
        }
        for (int i = 0; i < 2 * rows - 1; i++) {
            int sz = i < rows ? i + 1 : 2 * rows - i - 1;
            int r = i < rows ? 0 : i + 1 - rows;
            int c = i < rows ? i : rows - 1;
            for (int j = 0; j < sz; j++) {
                sum[i] += b[r + j][c - j];
                // System.out.print(b[r + j][c - j] + " ");
            }
            // System.out.println();
        }
    }    
}
