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

public class Round260 {

    public static void main(String[] args) {

        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(in, out);
        out.close();
    }
}

/*
 * My love has gone away,
 * 
 * quietly after a hundered days.
 * 
 * This is what's she has always said she won't stay
 * 
 * for more than what she can repay.
 * 
 * I can still hear her say
 * 
 * there that I'm not hearing tender play
 * 
 * The day she let me kiss her was a display,
 * 
 * of love to those who she betray.
 */
class TaskE {
    List<Integer>[] g;
    int[] parents;
    int[] value;
    int n;

    public void solve(InputReader in, PrintWriter out) {
        n = in.nextInt();
        int q = in.nextInt();
        g = new ArrayList[n];
        parents = new int[n];
        value = new int[n];

        Arrays.fill(parents, -1);
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<Integer>();
            value[i] = in.nextInt();
        }

        int vi;
        int ui;
        for (int i = 0; i < n - 1; i++) {
            vi = in.nextInt() - 1;
            ui = in.nextInt() - 1;
            g[vi].add(ui);
            g[ui].add(vi);
        }

        dfs(0, 0);
        parents[0] = -1;
        int v, w, type;
        int max;
        int k;
        for (int i = 0; i < q; i++) {
            type = in.nextInt();
            if (type == 1) {
                max = -1;
                v = in.nextInt() - 1;
                k = parents[v];
                while (k != -1) {
                    // out.println("dfs " + k);
                    if (gcd(value[k], value[v]) > 1 && k != v) {
                        max = k + 1;
                        break;
                    }
                    k = parents[k];
                }
                out.println(max);

            } else {
                v = in.nextInt() - 1;
                w = in.nextInt();
                value[v] = w;
            }
        }
    }

    private void dfs(int i, int parent) {
        parents[i] = parent;
        for (int u : g[i]) {
            if (parents[u] == -1)
                dfs(u, i);
        }
    }

    private int gcd(int a, int b) {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }
}

class TaskB {

    public void solve(InputReader in, PrintWriter out) {
        int n = in.nextInt();
        long res = 0;
        long energy = 0;
        int prev = 0;
        int cur = in.nextInt();
        res -= cur;
        prev = cur;

        for (int i = 1; i < n; i++) {
            cur = in.nextInt();
            energy += prev - cur;
            if (energy < 0) {
                res += energy;
                energy = 0;
            }
            prev = cur;
        }
        out.println(res * -1);
    }
}

class TaskD {

    int[][] a;
    int n;
    int k;

    public void solve(InputReader in, PrintWriter out) {
        n = in.nextInt();
        k = in.nextInt();
        int temp;

        a = new int[k][n];

        for (int i = 0; i < n; i++) {
            a[0][i] = in.nextInt() - 1;
        }

        for (int i = 1; i < k; i++) {
            for (int j = 0; j < n; j++) {
                temp = in.nextInt();
                a[i][temp - 1] = j;
            }
        }

        int res = calLength();
        out.println(res);

    }

    private int calLength() {
        int[] dp = new int[n];
        int res = 1;
        int temp;
        int in;
        Arrays.fill(dp, 1);

        for (int m = n - 2; m >= 0; m--) {
            temp = a[0][m];
            for (int i = m + 1; i < n; i++) {
                in = a[0][i];
                if (check(in, temp)) {
                    dp[m] = Math.max(dp[i] + 1, dp[m]);
                }
            }
            res = Math.max(res, dp[m]);
        }
        return res;
    }

    private boolean check(int in, int p) {
        for (int i = 1; i < k; i++) {
            if (a[i][in] < a[i][p])
                return false;
        }
        return true;
    }
}

class TaskC {

    public void solve(InputReader in, PrintWriter out) {
        int n = in.nextInt();
        long[][] a = new long[n][n];
        long[][] b = new long[n][n];
        long[][] s = new long[n][n];
        long temp;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temp = in.nextInt();
                s[i][j] -= temp;
                if (i > 0 && j < n - 1) {
                    a[i][j] = temp + a[i - 1][j + 1];
                } else {
                    a[i][j] = temp;
                }
                if (i > 0 && j > 0) {
                    b[i][j] = temp + b[i - 1][j - 1];

                } else {
                    b[i][j] = temp;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j + i >= n) {
                    temp = a[n - 1][j - (n - 1 - i)];
                } else {
                    temp = a[i + j][0];
                }
                s[i][j] += temp;
                if (i + (n - 1 - j) >= n) {
                    temp = b[n - 1][n - 1 - i + j];
                } else {
                    temp = b[i + (n - 1 - j)][n - 1];
                }
                s[i][j] += temp;
            }
        }

        long maxOdd = 0;
        int x1 = 0, y1 = 0;
        long maxEven = 0;
        int x2 = 0, y2 = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if ((i + j) % 2 == 0 && s[i][j] >= maxEven) {
                    maxEven = s[i][j];
                    x1 = i + 1;
                    y1 = j + 1;
                }
                if ((i + j) % 2 == 1 && s[i][j] >= maxOdd) {
                    maxOdd = s[i][j];
                    x2 = i + 1;
                    y2 = j + 1;
                }
            }
        }
        out.println(maxOdd + maxEven);
        out.println(x1 + " " + y1 + " " + x2 + " " + y2);
    }
}
/*
 * How can I put someone to the test,
 * 
 * when I thought I got the best.
 * 
 * Untill the taste of bitterness then I regret
 * 
 * but still that I won't detest,
 * 
 * the love I can't forget,
 * 
 * like someone who has left.
 * 
 * How can i leave someone for the rest
 * 
 * when i'm alone facing the best
 * 
 * Untill they take some try to reason i regret
 * 
 * But still that i won't detest
 * 
 * who i can never forget
 * 
 * like someone i once met ..
 */

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

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

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}
