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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Washoum
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        inputClass in = new inputClass(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CGargariAndBishops solver = new CGargariAndBishops();
        solver.solve(1, in, out);
        out.close();
    }

    static class CGargariAndBishops {
        public void solve(int testNumber, inputClass sc, PrintWriter out) {
            int n = sc.nextInt();
            int[][] grid = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    grid[i][j] = sc.nextInt();
                }
            }
            long[][] max = new long[n][n];
            long[][] sum1 = new long[n][n];
            for (int i = 0; i < n; i++) {
                sum1[0][i] = grid[0][i];
                sum1[i][0] = grid[i][0];
            }
            for (int i = 1; i < n; i++) {
                for (int j = 1; j < n; j++) {
                    sum1[i][j] = sum1[i - 1][j - 1] + grid[i][j];
                    max[i][j] += sum1[i][j];
                }
            }
            for (int i = 0; i < n; i++) {
                sum1[0][i] = grid[0][i];
                sum1[i][n - 1] = grid[i][n - 1];
            }
            for (int i = 1; i < n; i++) {
                for (int j = n - 2; j >= 0; j--) {
                    sum1[i][j] = sum1[i - 1][j + 1] + grid[i][j];
                    max[i][j] += sum1[i][j];
                }
            }
            for (int i = 0; i < n; i++) {
                sum1[n - 1][i] = grid[n - 1][i];
                sum1[i][0] = grid[i][0];
            }
            for (int i = n - 2; i >= 0; i--) {
                for (int j = 1; j < n; j++) {
                    sum1[i][j] = sum1[i + 1][j - 1] + grid[i][j];
                    max[i][j] += sum1[i][j];
                }
            }
            for (int i = 0; i < n; i++) {
                sum1[n - 1][i] = grid[n - 1][i];
                sum1[i][n - 1] = grid[i][n - 1];
            }
            for (int i = n - 2; i >= 0; i--) {
                for (int j = n - 2; j >= 0; j--) {
                    sum1[i][j] = sum1[i + 1][j + 1] + grid[i][j];
                    max[i][j] += sum1[i][j];
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    max[i][j] -= 3L * grid[i][j];
                }
            }
            long bestw = -1;
            int xw = -1;
            int yw = -1;
            long bestb = -1;
            int xb = -1;
            int yb = -1;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if ((i + j) % 2 == 0) {
                        if (max[i][j] > bestw) {
                            bestw = max[i][j];
                            xw = i + 1;
                            yw = j + 1;
                        }
                    } else {
                        if (max[i][j] > bestb) {
                            bestb = max[i][j];
                            xb = i + 1;
                            yb = j + 1;
                        }
                    }
                }
            }
            out.println(bestb + bestw);
            out.println(xb + " " + yb + " " + xw + " " + yw);
        }

    }

    static class inputClass {
        BufferedReader br;
        StringTokenizer st;

        public inputClass(InputStream in) {

            br = new BufferedReader(new InputStreamReader(in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

