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.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.Comparator;
import java.util.Collections;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(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, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            int arr[][] = new int[n][n];

            long dp1[] = new long[5 * n];
            long dp2[] = new long[5 * n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    arr[i][j] = in.scanInt();
                    dp1[i + j] += arr[i][j];
                    dp2[i - j + n] += arr[i][j];
                }
            }
            ArrayList<pair> oo = new ArrayList<>();
            ArrayList<pair> ee = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    long ss = dp1[i + j] + dp2[i - j + n] - arr[i][j];
                    if ((i + j) % 2 == 1) oo.add(new pair(i, j, ss));
                    else ee.add(new pair(i, j, ss));
                }
            }

            Collections.sort(oo, new Comparator<pair>() {

                public int compare(pair o1, pair o2) {
                    if (o2.sum > o1.sum) return 1;
                    else if (o2.sum < o1.sum) return -1;
                    else return 0;
                }
            });

            Collections.sort(ee, new Comparator<pair>() {

                public int compare(pair o1, pair o2) {
                    if (o2.sum > o1.sum) return 1;
                    else if (o2.sum < o1.sum) return -1;
                    else return 0;
                }
            });

            out.println(oo.get(0).sum + ee.get(0).sum);
            out.print(oo.get(0).i + 1 + " ");
            out.print(oo.get(0).j + 1 + " ");
            out.print(ee.get(0).i + 1 + " ");
            out.print(ee.get(0).j + 1 + " ");

        }

        class pair {
            int i;
            int j;
            long sum = 0;

            public pair(int i, int j, long sum) {
                this.i = i;
                this.j = j;
                this.sum = sum;
            }

        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 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') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

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

    }
}

