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.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {

    public static void main(String[] args) {
        if (args.length > 0 && args[0].toLowerCase().equals("local")) {
            try {
                System.setIn(new FileInputStream("input.txt"));
                System.setOut(new PrintStream(new File("output.txt")));
            } catch (IOException exc) {
            }
        }
        Task task = new Task();
        task.solve();
    }

    public static class Task {
        static final long MOD = (long) 1e9 + 7;
        static final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        public void solve() {
            try {
                Scan sc = new Scan();
                int n = (int) sc.scanLong();

                int[][] grid = new int[n][n];
                long[] backSlash = new long[2 * n - 1];
                long[] forSlash = new long[2 * n - 1];
                for (int i = 0; i < n; ++i) {
                    for (int j = 0; j < n; ++j) {
                        grid[i][j] = (int) sc.scanLong();
                        forSlash[i + j] += grid[i][j];
                        int diff = i - j;
                        if (diff >= 0) {
                            backSlash[diff] += grid[i][j];
                        } else {
                            backSlash[Math.abs(diff) + n - 1] += grid[i][j];
                        }
                    }
                }
                long bestBlack = -1;
                long bestBlackX = -1;
                long bestBlackY = -1;
                for (int i = 0; i < n; ++i) {
                    for (int j = (i % 2); j < n; j += 2) {
                        long black_val = forSlash[i + j];
                        int diff = i - j;
                        if (diff >= 0) {
                            black_val += backSlash[diff];
                        } else {
                            black_val += backSlash[Math.abs(diff) + n - 1];
                        }
                        black_val -= grid[i][j];
                        if (black_val > bestBlack) {
                            bestBlack = black_val;
                            bestBlackX = i + 1;
                            bestBlackY = j + 1;
                        }
                    }
                }
                long bestWhite = -1;
                long bestWhiteX = -1;
                long bestWhiteY = -1;
                for (int i = 0; i < n; ++i) {
                    for (int j = 1 ^ (i % 2); j < n; j += 2) {
                        long white_val = forSlash[i + j];
                        int diff = i - j;
                        if (diff >= 0) {
                            white_val += backSlash[diff];
                        } else {
                            white_val += backSlash[Math.abs(diff) + n - 1];
                        }
                        white_val -= grid[i][j];

                        if (white_val > bestWhite) {
                            bestWhite = white_val;
                            bestWhiteX = i + 1;
                            bestWhiteY = j + 1;
                        }
                    }
                }

                out.println((bestWhite + bestBlack) + "\n" + bestBlackX + " " + bestBlackY + " " + bestWhiteX + " "
                        + bestWhiteY);
            } finally {
                out.close();
            }
        }

        private void debug(Object... x) {
            StringBuilder sb = new StringBuilder();
            for (Object o : x)
                sb.append(String.valueOf(o)).append(" ");
            out.println(sb);
        }
    }

    public static class Scan {
        private byte[] buf = new byte[1024];
        private int index;
        private InputStream in;
        private int total;

        public Scan() {
            in = System.in;
        }

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

        public long scanLong() {
            long integer = 0;
            int n = scan();
            while (isWhiteSpace(n))
                n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                } else
                    throw new InputMismatchException();
            }
            return neg * integer;
        }

        public double scanDouble() {
            double doub = 0;
            int n = scan();
            while (isWhiteSpace(n))
                n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n) && n != '.') {
                if (n >= '0' && n <= '9') {
                    doub *= 10;
                    doub += n - '0';
                    n = scan();
                } else
                    throw new InputMismatchException();
            }
            if (n == '.') {
                n = scan();
                double temp = 1;
                while (!isWhiteSpace(n)) {
                    if (n >= '0' && n <= '9') {
                        temp /= 10;
                        doub += (n - '0') * temp;
                        n = scan();
                    } else
                        throw new InputMismatchException();
                }
            }
            return doub * neg;
        }

        public String scanString() {
            StringBuilder sb = new StringBuilder();
            int n = scan();
            while (isWhiteSpace(n))
                n = scan();
            while (!isWhiteSpace(n)) {
                sb.append((char) n);
                n = scan();
            }
            return sb.toString();
        }

        public char scanChar() {
            int n = scan();
            while (isWhiteSpace(n))
                n = scan();
            return (char) n;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1)
                return true;
            return false;
        }
    }
}