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.awt.*;
import java.awt.geom.Arc2D;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;
import java.util.List;
import static java.lang.Math.sqrt;
 public class Question {

    public static void main(String[] args) {
        new Question(System.in, System.out);

/*        for (int i = 0; i < 10; i++)
            System.out.println("i : " + i + ", (ch) I : " + ((char) i));*/
    }



    static class News{
        long ne;
        long nw;
        long se;
        long sw;

    }
    static class Solver {
        int n;
        int[][] value;
        News[][] allDirection;
        InputReader in;
        PrintWriter out;

        void func1(News[][] allDirection, int[][] values) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i - 1 >= 0) {
                        if (j - 1 >= 0)
                            allDirection[i][j].nw = allDirection[i - 1][j - 1].nw + value[i - 1][j - 1];
                        else {
                            allDirection[i][j].nw = 0;
                        }
                        if (j + 1 < n)
                            allDirection[i][j].ne = allDirection[i - 1][j + 1].ne + value[i - 1][j + 1];
                        else {
                            allDirection[i][j].ne = 0;
                        }

                    } else {
                        allDirection[i][j].nw = 0;
                        allDirection[i][j].ne = 0;
                    }
                }
            }
        }

        void func2(News[][] allDirection, int[][] values) {
            for (int i = n-1; i >=0; i--) {
                for (int j = n-1; j >=0; j--) {
                    if (i + 1 < n) {
                        if (j - 1 >= 0)
                            allDirection[i][j].sw = allDirection[i + 1][j - 1].sw + value[i + 1][j - 1];
                        else {
                            allDirection[i][j].sw = 0;
                        }
                        if (j + 1 < n)
                            allDirection[i][j].se = allDirection[i + 1][j + 1].se + value[i + 1][j + 1];
                        else {
                            allDirection[i][j].se = 0;
                        }

                    } else {
                        allDirection[i][j].sw = 0;
                        allDirection[i][j].se = 0;
                    }
                }
            }
        }

        void solve() throws IOException {
            n = in.nextInt();
            value = new int[n][n];
            allDirection = new News[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    value[i][j] = in.nextInt();
                    allDirection[i][j] =  new News();
                }
            }



            func1(allDirection, value);
            func2(allDirection, value);
            int x=-1,y=-1;
            long max=-1;
            /*for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(allDirection[i][j].ne + allDirection[i][j].nw + allDirection[i][j].se + allDirection[i][j].sw + " ");
                }
                System.out.println("");
            }*/
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (max < value[i][j] + allDirection[i][j].ne + allDirection[i][j].nw + allDirection[i][j].se + allDirection[i][j].sw){
                        max = value[i][j] + allDirection[i][j].ne + allDirection[i][j].nw + allDirection[i][j].se + allDirection[i][j].sw;
                        x=i+1;
                        y=j+1;
                    }
                }
            }
            int x1=-1,y1=-1;
            long max1=-1;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (max1 < value[i][j] + allDirection[i][j].ne + allDirection[i][j].nw + allDirection[i][j].se + allDirection[i][j].sw && ((x+y)%2!=(i+j)%2)){
                        max1 = value[i][j] + allDirection[i][j].ne + allDirection[i][j].nw + allDirection[i][j].se + allDirection[i][j].sw;
                        x1=i+1;
                        y1=j+1;
                    }
                }
            }

            System.out.println(max+max1);
            System.out.println(x+" "+y+" "+x1+" "+y1);

        }
        Solver(InputReader in, PrintWriter out) {
            this.in = in;
            this.out = out;
        }

    }

    static class InputReader {
        private InputStream stream;
        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 = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        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 & 15;

                c = read();
            } while (!isSpaceChar(c));

            return res * sgn;
        }

        public int[] nextIntArray(int arraySize) {
            int array[] = new int[arraySize];

            for (int i = 0; i < arraySize; i++)
                array[i] = nextInt();

            return array;
        }

        public long nextLong() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sign = 1;

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

                c = read();
            }

            long result = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                result *= 10;
                result += c & 15;

                c = read();
            } while (!isSpaceChar(c));

            return result * sign;
        }

        public long[] nextLongArray(int arraySize) {
            long array[] = new long[arraySize];

            for (int i = 0; i < arraySize; i++)
                array[i] = nextLong();

            return array;
        }

        public float nextFloat() {
            float result, div;
            byte c;

            result = 0;
            div = 1;
            c = (byte) read();

            while (c <= ' ')
                c = (byte) read();

            boolean isNegative = (c == '-');

            if (isNegative)
                c = (byte) read();

            do {
                result = result * 10 + c - '0';
            } while ((c = (byte) read()) >= '0' && c <= '9');

            if (c == '.')
                while ((c = (byte) read()) >= '0' && c <= '9')
                    result += (c - '0') / (div *= 10);

            if (isNegative)
                return -result;

            return result;
        }

        public double nextDouble() {
            double ret = 0, div = 1;
            byte c = (byte) read();

            while (c <= ' ')
                c = (byte) read();

            boolean neg = (c == '-');

            if (neg)
                c = (byte) read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = (byte) read()) >= '0' && c <= '9');

            if (c == '.')
                while ((c = (byte) read()) >= '0' && c <= '9')
                    ret += (c - '0') / (div *= 10);

            if (neg)
                return -ret;

            return ret;
        }

        public String next() {
            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 boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String nextLine() {
            int c = read();

            StringBuilder result = new StringBuilder();

            do {
                result.appendCodePoint(c);

                c = read();
            } while (!isNewLine(c));

            return result.toString();
        }

        public boolean isNewLine(int c) {
            return c == '\n';
        }

        public void close() {
            try {
                stream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

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

    }

    Question(InputStream inputStream, OutputStream outputStream) {
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver(in, out);

        try {
            solver.solve();
        } catch (IOException e) {
            e.printStackTrace();
        }
        in.close();
        out.flush();
        out.close();
    }

}