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

/**
 * Created by hama_du on 2014/08/09.
 */
public class ProblemC {
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        long[][] z = new long[n][n];
        for (int i = 0 ; i < n ; i++) {
            for (int j = 0 ; j < n ; j++) {
                z[i][j] = in.nextInt();
            }
        }

        long[] down = new long[2*n+1];
        for (int i = 0 ; i < n ; i++) {
            for (int j = 0; j < n; j++) {
                down[i-j+n-1] += z[i][j];
            }
        }

        long[] up = new long[2*n+1];
        for (int i = 0 ; i < n ; i++) {
            for (int j = 0; j < n; j++) {
                up[i+j] += z[i][j];
            }
        }


        long odd = -1;
        int oi = -1;
        int oj = -1;
        long even = -1;
        int ei = -1;
        int ej = -1;
        for (int i = 0 ; i < n ; i++) {
            for (int j = 0; j < n; j++) {
                int d = (i-j)+n-1;
                int u = i+j;
                long val = down[d] + up[u] - z[i][j];
                if ((i+j)%2 == 0) {
                    if (even < val) {
                        even = val;
                        ei = i+1;
                        ej = j+1;
                    }
                } else {
                    if (odd < val) {
                        odd = val;
                        oi = i+1;
                        oj = j+1;
                    }
                }
            }
        }

        out.println(odd + even);
        out.println(String.format("%d %d %d %d", oi, oj, ei, ej));
        out.flush();
    }

    private static boolean possible(long med, long[] h) {
        int n = h.length;
        long now = med;
        long prev = 0;
        for (int i = 0 ; i < n ; i++) {
            long en = prev - h[i];
            now += en;
            if (now < 0) {
                return false;
            }
            prev = h[i];
        }
        return true;
    }


    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

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

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

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

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

}
