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.*;
import java.lang.reflect.Array;
import java.util.Arrays;

public class GargariAndBishops {
    static class InputReader {

        /**
         * The default size of the InputReader's buffer is 2^16 -> 65,536 characters
         */
        private static final int DEFAULT_BUFFER_SIZE = 1 << 16; // Change this to increase your input size //

        /**
         * The default stream for the InputReader is standard input.
         */
        private static final InputStream DEFAULT_STREAM = System.in;

        /**
         * The maximum number of accurate decimal digits the method {@link #nextDoubleFast() nextDoubleFast()} can read.
         * Currently this value is set to 21 because it is the maximum number of digits a double precision float can have at the moment.
         */
        private static final int MAX_DECIMAL_PRECISION = 21;

        // 'c' is used to refer to the current character in the stream
        private int c;

        // Variables associated with the byte buffer.
        private byte[] buf;
        private int bufferSize, bufIndex, numBytesRead;

        private InputStream stream;

        // End Of File (EOF) character
        private static final byte EOF = -1;

        // New line character: '\n'
        private static final byte NEW_LINE = 10;

        // Carriage return character: '\r'
        private static final byte CARRIAGE_RETURN = 13;

        // Space character: ' '
        private static final byte SPACE = 32;

        // Dash character: '-'
        private static final byte DASH = 45;

        // Dot character: '.'
        private static final byte DOT = 46;

        // A reusable character buffer when reading string data.
        private char[] charBuffer;

        // Primitive data type lookup tables used for optimizations
        private static byte[] bytes = new byte[58];
        private static int[] ints = new int[58];
        private static char[] chars = new char[128];

        static {
            char ch = ' ';
            int value = 0;
            byte _byte = 0;
            for (int i = 48; i < 58; i++) bytes[i] = _byte++;
            for (int i = 48; i < 58; i++) ints[i] = value++;
            for (int i = 32; i < 128; i++) chars[i] = ch++;
        }

        // Primitive double lookup table used for optimizations.
        private static final double[][] doubles = {
                {0.0d, 0.00d, 0.000d, 0.0000d, 0.00000d, 0.000000d, 0.0000000d, 0.00000000d, 0.000000000d, 0.0000000000d, 0.00000000000d, 0.000000000000d, 0.0000000000000d, 0.00000000000000d, 0.000000000000000d, 0.0000000000000000d, 0.00000000000000000d, 0.000000000000000000d, 0.0000000000000000000d, 0.00000000000000000000d, 0.000000000000000000000d},
                {0.1d, 0.01d, 0.001d, 0.0001d, 0.00001d, 0.000001d, 0.0000001d, 0.00000001d, 0.000000001d, 0.0000000001d, 0.00000000001d, 0.000000000001d, 0.0000000000001d, 0.00000000000001d, 0.000000000000001d, 0.0000000000000001d, 0.00000000000000001d, 0.000000000000000001d, 0.0000000000000000001d, 0.00000000000000000001d, 0.000000000000000000001d},
                {0.2d, 0.02d, 0.002d, 0.0002d, 0.00002d, 0.000002d, 0.0000002d, 0.00000002d, 0.000000002d, 0.0000000002d, 0.00000000002d, 0.000000000002d, 0.0000000000002d, 0.00000000000002d, 0.000000000000002d, 0.0000000000000002d, 0.00000000000000002d, 0.000000000000000002d, 0.0000000000000000002d, 0.00000000000000000002d, 0.000000000000000000002d},
                {0.3d, 0.03d, 0.003d, 0.0003d, 0.00003d, 0.000003d, 0.0000003d, 0.00000003d, 0.000000003d, 0.0000000003d, 0.00000000003d, 0.000000000003d, 0.0000000000003d, 0.00000000000003d, 0.000000000000003d, 0.0000000000000003d, 0.00000000000000003d, 0.000000000000000003d, 0.0000000000000000003d, 0.00000000000000000003d, 0.000000000000000000003d},
                {0.4d, 0.04d, 0.004d, 0.0004d, 0.00004d, 0.000004d, 0.0000004d, 0.00000004d, 0.000000004d, 0.0000000004d, 0.00000000004d, 0.000000000004d, 0.0000000000004d, 0.00000000000004d, 0.000000000000004d, 0.0000000000000004d, 0.00000000000000004d, 0.000000000000000004d, 0.0000000000000000004d, 0.00000000000000000004d, 0.000000000000000000004d},
                {0.5d, 0.05d, 0.005d, 0.0005d, 0.00005d, 0.000005d, 0.0000005d, 0.00000005d, 0.000000005d, 0.0000000005d, 0.00000000005d, 0.000000000005d, 0.0000000000005d, 0.00000000000005d, 0.000000000000005d, 0.0000000000000005d, 0.00000000000000005d, 0.000000000000000005d, 0.0000000000000000005d, 0.00000000000000000005d, 0.000000000000000000005d},
                {0.6d, 0.06d, 0.006d, 0.0006d, 0.00006d, 0.000006d, 0.0000006d, 0.00000006d, 0.000000006d, 0.0000000006d, 0.00000000006d, 0.000000000006d, 0.0000000000006d, 0.00000000000006d, 0.000000000000006d, 0.0000000000000006d, 0.00000000000000006d, 0.000000000000000006d, 0.0000000000000000006d, 0.00000000000000000006d, 0.000000000000000000006d},
                {0.7d, 0.07d, 0.007d, 0.0007d, 0.00007d, 0.000007d, 0.0000007d, 0.00000007d, 0.000000007d, 0.0000000007d, 0.00000000007d, 0.000000000007d, 0.0000000000007d, 0.00000000000007d, 0.000000000000007d, 0.0000000000000007d, 0.00000000000000007d, 0.000000000000000007d, 0.0000000000000000007d, 0.00000000000000000007d, 0.000000000000000000007d},
                {0.8d, 0.08d, 0.008d, 0.0008d, 0.00008d, 0.000008d, 0.0000008d, 0.00000008d, 0.000000008d, 0.0000000008d, 0.00000000008d, 0.000000000008d, 0.0000000000008d, 0.00000000000008d, 0.000000000000008d, 0.0000000000000008d, 0.00000000000000008d, 0.000000000000000008d, 0.0000000000000000008d, 0.00000000000000000008d, 0.000000000000000000008d},
                {0.9d, 0.09d, 0.009d, 0.0009d, 0.00009d, 0.000009d, 0.0000009d, 0.00000009d, 0.000000009d, 0.0000000009d, 0.00000000009d, 0.000000000009d, 0.0000000000009d, 0.00000000000009d, 0.000000000000009d, 0.0000000000000009d, 0.00000000000000009d, 0.000000000000000009d, 0.0000000000000000009d, 0.00000000000000000009d, 0.000000000000000000009d}
        };

        /**
         * Create an InputReader that reads from standard input.
         */
        public InputReader() {
            this(DEFAULT_STREAM, DEFAULT_BUFFER_SIZE);
        }

        /**
         * Create an InputReader that reads from standard input.
         *
         * @param bufferSize The buffer size for this input reader.
         */
        public InputReader(int bufferSize) {
            this(DEFAULT_STREAM, bufferSize);
        }

        /**
         * Create an InputReader that reads from standard input.
         *
         * @param stream Takes an InputStream as a parameter to read from.
         */
        public InputReader(InputStream stream) {
            this(stream, DEFAULT_BUFFER_SIZE);
        }

        /**
         * Create an InputReader that reads from standard input.
         *
         * @param stream     Takes an {@link InputStream#InputStream() InputStream} as a parameter to read from.
         * @param bufferSize The size of the buffer to use.
         */
        public InputReader(InputStream stream, int bufferSize) {
            if (stream == null || bufferSize <= 0)
                throw new IllegalArgumentException();
            buf = new byte[bufferSize];
            charBuffer = new char[128];
            this.bufferSize = bufferSize;
            this.stream = stream;
        }

        /**
         * Reads a single character from the input stream.
         *
         * @return Returns the byte value of the next character in the buffer and EOF
         * at the end of the stream.
         * @throws IOException throws exception if there is no more data to read
         */
        private byte read() throws IOException {

            if (numBytesRead == EOF) throw new IOException();

            if (bufIndex >= numBytesRead) {
                bufIndex = 0;
                numBytesRead = stream.read(buf);
                if (numBytesRead == EOF)
                    return EOF;
            }

            return buf[bufIndex++];
        }

        /**
         * Read values from the input stream until you reach a character with a
         * higher ASCII value than 'token'.
         *
         * @param token The token is a value which we use to stop reading junk out of
         *              the stream.
         * @return Returns 0 if a value greater than the token was reached or -1 if
         * the end of the stream was reached.
         * @throws IOException Throws exception at end of stream.
         */
        private int readJunk(int token) throws IOException {

            if (numBytesRead == EOF) return EOF;

            // Seek to the first valid position index
            do {

                while (bufIndex < numBytesRead) {
                    if (buf[bufIndex] > token) return 0;
                    bufIndex++;
                }

                // reload buffer
                numBytesRead = stream.read(buf);
                if (numBytesRead == EOF) return EOF;
                bufIndex = 0;

            } while (true);

        }

        /**
         * Reads a single byte from the input stream.
         *
         * @return The next byte in the input stream
         * @throws IOException Throws exception at end of stream.
         */
        public byte nextByte() throws IOException {
            return (byte) nextInt();
        }

        /**
         * Reads a 32 bit signed integer from input stream.
         *
         * @return The next integer value in the stream.
         * @throws IOException Throws exception at end of stream.
         */
        public int nextInt() throws IOException {

            if (readJunk(DASH - 1) == EOF) throw new IOException();
            int sgn = 1, res = 0;

            c = buf[bufIndex];
            if (c == DASH) {
                sgn = -1;
                bufIndex++;
            }

            do {

                while (bufIndex < numBytesRead) {
                    if (buf[bufIndex] > SPACE) {
                        res = (res << 3) + (res << 1);
                        res += ints[buf[bufIndex++]];
                    } else {
                        bufIndex++;
                        return res * sgn;
                    }
                }

                // Reload buffer
                numBytesRead = stream.read(buf);
                if (numBytesRead == EOF) return res * sgn;
                bufIndex = 0;

            } while (true);

        }

        /**
         * Reads a 64 bit signed long from input stream.
         *
         * @return The next long value in the stream.
         * @throws IOException Throws exception at end of stream.
         */
        public long nextLong() throws IOException {

            if (readJunk(DASH - 1) == EOF) throw new IOException();
            int sgn = 1;
            long res = 0L;
            c = buf[bufIndex];
            if (c == DASH) {
                sgn = -1;
                bufIndex++;
            }

            do {

                while (bufIndex < numBytesRead) {
                    if (buf[bufIndex] > SPACE) {
                        res = (res << 3) + (res << 1);
                        res += ints[buf[bufIndex++]];
                    } else {
                        bufIndex++;
                        return res * sgn;
                    }
                }

                // Reload buffer
                numBytesRead = stream.read(buf);
                if (numBytesRead == EOF) return res * sgn;
                bufIndex = 0;

            } while (true);

        }

        /**
         * Doubles the size of the internal char buffer for strings
         */
        private void doubleCharBufferSize() {
            char[] newBuffer = new char[charBuffer.length << 1];
            for (int i = 0; i < charBuffer.length; i++) newBuffer[i] = charBuffer[i];
            charBuffer = newBuffer;
        }

        /**
         * Reads a line from the input stream.
         *
         * @return Returns a line from the input stream in the form a String not
         * including the new line character. Returns <code>null</code> when there are
         * no more lines.
         * @throws IOException Throws IOException when something terrible happens.
         */
        public String nextLine() throws IOException {

            try {
                c = read();
            } catch (IOException e) {
                return null;
            }
            if (c == NEW_LINE) return ""; // Empty line
            if (c == EOF) return null; // EOF

            int i = 0;
            charBuffer[i++] = (char) c;

            do {

                while (bufIndex < numBytesRead) {
                    if (buf[bufIndex] != NEW_LINE && buf[bufIndex] != CARRIAGE_RETURN) {
                        if (i == charBuffer.length) doubleCharBufferSize();
                        charBuffer[i++] = (char) buf[bufIndex++];
                    } else {
                        if(buf[bufIndex] == CARRIAGE_RETURN) bufIndex++;
                        bufIndex++;
                        return new String(charBuffer, 0, i);
                    }
                }

                // Reload buffer
                numBytesRead = stream.read(buf);
                if (numBytesRead == EOF)
                    return new String(charBuffer, 0, i);
                bufIndex = 0;

            } while (true);

        }

        // Reads a string of characters from the input stream.
        // The delimiter separating a string of characters is set to be:
        // any ASCII value <= 32 meaning any spaces, new lines, EOF, tabs...
        public String nextString() throws IOException {
            if (numBytesRead == EOF) return null;
            if (readJunk(SPACE) == EOF) return null;

            for (int i = 0; ; ) {
                while (bufIndex < numBytesRead) {
                    if (buf[bufIndex] > SPACE) {
                        if (i == charBuffer.length) doubleCharBufferSize();
                        charBuffer[i++] = (char) buf[bufIndex++];
                    } else {
                        bufIndex++;
                        return new String(charBuffer, 0, i);
                    }
                }

                // Reload buffer
                numBytesRead = stream.read(buf);
                if (numBytesRead == EOF) return new String(charBuffer, 0, i);
                bufIndex = 0;
            }
        }

        // Returns an exact value a double value from the input stream.
        public double nextDouble() throws IOException {
            String doubleVal = nextString();
            if (doubleVal == null) throw new IOException();
            return Double.valueOf(doubleVal);
        }

        // Very quickly reads a double value from the input stream (~3x faster than nextDouble()). However,
        // this method may provide a slightly less accurate reading than .nextDouble() if there are a lot
        // of digits (~16+). In particular, it will only read double values with at most 21 digits after
        // the decimal point and the reading my be as inaccurate as ~5*10^-16 from the true value.
        public double nextDoubleFast() throws IOException {
            c = read();
            int sgn = 1;
            while (c <= SPACE) c = read(); // while c is either: ' ', '\n', EOF
            if (c == DASH) {
                sgn = -1;
                c = read();
            }
            double res = 0.0;
            // while c is not: ' ', '\n', '.' or -1
            while (c > DOT) {
                res *= 10.0;
                res += ints[c];
                c = read();
            }
            if (c == DOT) {
                int i = 0;
                c = read();
                // while c is digit and we are less than the maximum decimal precision
                while (c > SPACE && i < MAX_DECIMAL_PRECISION) {
                    res += doubles[ints[c]][i++];
                    c = read();
                }
            }
            return res * sgn;
        }

        // Read an array of n byte values
        public byte[] nextByteArray(int n) throws IOException {
            byte[] ar = new byte[n];
            for (int i = 0; i < n; i++) ar[i] = nextByte();
            return ar;
        }

        // Read an integer array of size n
        public int[] nextIntArray(int n) throws IOException {
            int[] ar = new int[n];
            for (int i = 0; i < n; i++) ar[i] = nextInt();
            return ar;
        }

        // Read a long array of size n
        public long[] nextLongArray(int n) throws IOException {
            long[] ar = new long[n];
            for (int i = 0; i < n; i++) ar[i] = nextLong();
            return ar;
        }

        // read an of doubles of size n
        public double[] nextDoubleArray(int n) throws IOException {
            double[] ar = new double[n];
            for (int i = 0; i < n; i++) ar[i] = nextDouble();
            return ar;
        }

        // Quickly read an array of doubles
        public double[] nextDoubleArrayFast(int n) throws IOException {
            double[] ar = new double[n];
            for (int i = 0; i < n; i++) ar[i] = nextDoubleFast();
            return ar;
        }

        // Read a string array of size n
        public String[] nextStringArray(int n) throws IOException {
            String[] ar = new String[n];
            for (int i = 0; i < n; i++) {
                String str = nextString();
                if (str == null) throw new IOException();
                ar[i] = str;
            }
            return ar;
        }

        // Read a 1-based byte array of size n+1
        public byte[] nextByteArray1(int n) throws IOException {
            byte[] ar = new byte[n + 1];
            for (int i = 1; i <= n; i++) ar[i] = nextByte();
            return ar;
        }

        // Read a 1-based integer array of size n+1
        public int[] nextIntArray1(int n) throws IOException {
            int[] ar = new int[n + 1];
            for (int i = 1; i <= n; i++) ar[i] = nextInt();
            return ar;
        }

        // Read a 1-based long array of size n+1
        public long[] nextLongArray1(int n) throws IOException {
            long[] ar = new long[n + 1];
            for (int i = 1; i <= n; i++) ar[i] = nextLong();
            return ar;
        }

        // Read a 1-based double array of size n+1
        public double[] nextDoubleArray1(int n) throws IOException {
            double[] ar = new double[n + 1];
            for (int i = 1; i <= n; i++) ar[i] = nextDouble();
            return ar;
        }

        // Quickly read a 1-based double array of size n+1
        public double[] nextDoubleArrayFast1(int n) throws IOException {
            double[] ar = new double[n + 1];
            for (int i = 1; i <= n; i++) ar[i] = nextDoubleFast();
            return ar;
        }

        // Read a 1-based string array of size n+1
        public String[] nextStringArray1(int n) throws IOException {
            String[] ar = new String[n + 1];
            for (int i = 1; i <= n; i++) ar[i] = nextString();
            return ar;
        }

        // Read a two dimensional matrix of bytes of size rows x cols
        public byte[][] nextByteMatrix(int rows, int cols) throws IOException {
            byte[][] matrix = new byte[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextByte();
            return matrix;
        }

        // Read a two dimensional matrix of ints of size rows x cols
        public int[][] nextIntMatrix(int rows, int cols) throws IOException {
            int[][] matrix = new int[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextInt();
            return matrix;
        }

        // Read a two dimensional matrix of longs of size rows x cols
        public long[][] nextLongMatrix(int rows, int cols) throws IOException {
            long[][] matrix = new long[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextLong();
            return matrix;
        }

        // Read a two dimensional matrix of doubles of size rows x cols
        public double[][] nextDoubleMatrix(int rows, int cols) throws IOException {
            double[][] matrix = new double[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextDouble();
            return matrix;
        }

        // Quickly read a two dimensional matrix of doubles of size rows x cols
        public double[][] nextDoubleMatrixFast(int rows, int cols) throws IOException {
            double[][] matrix = new double[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextDoubleFast();
            return matrix;
        }

        // Read a two dimensional matrix of Strings of size rows x cols
        public String[][] nextStringMatrix(int rows, int cols) throws IOException {
            String[][] matrix = new String[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextString();
            return matrix;
        }

        // Read a 1-based two dimensional matrix of bytes of size rows x cols
        public byte[][] nextByteMatrix1(int rows, int cols) throws IOException {
            byte[][] matrix = new byte[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++)
                for (int j = 1; j <= cols; j++)
                    matrix[i][j] = nextByte();
            return matrix;
        }

        // Read a 1-based two dimensional matrix of ints of size rows x cols
        public int[][] nextIntMatrix1(int rows, int cols) throws IOException {
            int[][] matrix = new int[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++)
                for (int j = 1; j <= cols; j++)
                    matrix[i][j] = nextInt();
            return matrix;
        }

        // Read a 1-based two dimensional matrix of longs of size rows x cols
        public long[][] nextLongMatrix1(int rows, int cols) throws IOException {
            long[][] matrix = new long[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++)
                for (int j = 1; j <= cols; j++)
                    matrix[i][j] = nextLong();
            return matrix;
        }

        // Read a 1-based two dimensional matrix of doubles of size rows x cols
        public double[][] nextDoubleMatrix1(int rows, int cols) throws IOException {
            double[][] matrix = new double[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++)
                for (int j = 1; j <= cols; j++)
                    matrix[i][j] = nextDouble();
            return matrix;
        }

        // Quickly read a 1-based two dimensional matrix of doubles of size rows x cols
        public double[][] nextDoubleMatrixFast1(int rows, int cols) throws IOException {
            double[][] matrix = new double[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++)
                for (int j = 1; j <= cols; j++)
                    matrix[i][j] = nextDoubleFast();
            return matrix;
        }

        // Read a 1-based two dimensional matrix of Strings of size rows x cols
        public String[][] nextStringMatrix1(int rows, int cols) throws IOException {
            String[][] matrix = new String[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++)
                for (int j = 1; j <= cols; j++)
                    matrix[i][j] = nextString();
            return matrix;
        }

        // Closes the input stream
        public void close() throws IOException {
            stream.close();
        }
    }

    // region variables
    static InputReader sc = new InputReader();
    static OutputStream outputStream = System.out;
    static PrintWriter w = new PrintWriter(outputStream);
    static long timeStart;
    // endregion

    private static void initiateIO()
            throws IOException {
        if (System.getProperty("ONLINE_JUDGE") == null) {
            try {
                w = new PrintWriter("output.txt");
                sc = new InputReader(new FileInputStream("input.txt"));
            } catch (Exception e) {
                throw new IOException();
            }
        }
    }

    public static void main(String[] args)
            throws IOException {

        initiateIO();

        solve();

        w.close();

    }

    static void solve() throws IOException {
        int n = sc.nextInt();
        long[][] matrix = sc.nextLongMatrix(n, n);
        long[] diag1 = new long[2*n-1];
        long[] diag2 = new long[2*n-1];


        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                diag1[i+j] += matrix[i][j];
                diag2[i-j+n-1] += matrix[i][j];
            }
        }
        long[][] val = new long[n][n];

        long bestOdd = -1; long bestEven = -1; int oddx = -1, oddy= -1, evex = -1, evey = -1;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                val[i][j] = diag1[i+j] + diag2[i-j+n-1] - matrix[i][j];
                long currVal = val[i][j];
                if(((i+j) & 1) == 0) {
                    if(currVal > bestEven) {
                        bestEven = currVal;
                        evex = i;
                        evey = j;
                    }
                } else {
                    if(currVal > bestOdd) {
                        bestOdd = currVal;
                        oddx = i;
                        oddy = j;
                    }
                }
            }
        }

        w.println((val[evex][evey] + val[oddx][oddy]));
        w.println((evex+1)+" "+(evey+1)+" "+(oddx+1)+" "+(oddy+1)+" ");



    }
}