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.util.*;
import java.io.*;

public class Task implements Runnable {
    static FastReader in;
    static PrintWriter out;

    static boolean ok(int t, int n) {
        return t >= 0 && t < n;
    }

    public void solve() throws IOException {
        int n = in.nextInt();
        int[][] cost = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cost[i][j] = in.nextInt();
            }
        }
        long[] r = new long[2 * n - 1];
        for (int i = 0; i < 2 * n - 1; ++i) {
            int x = Math.max(0, n - 1 - i);
            int y = Math.max(0, i - n + 1);
            while (ok(x, n) && ok(y, n)) {
                r[i] += cost[x][y];
                ++x;
                ++y;
            }
        }
        long[] l = new long[2 * n - 1];
        for (int i = 0; i < 2 * n - 1; ++i) {
            int x = Math.max(0, i - n + 1);
            int y = Math.min(n - 1, i);
            while (ok(x, n) && ok(y, n)) {
                l[i] += cost[x][y];
                ++x;
                --y;
            }
        }
        int x1 = -1;
        int y1 = -1;
        long res1 = -1;
        int x2 = -1;
        int y2 = -1;
        long res2 = -1;
        for (int i = 0; i < 2 * n - 1; ++i) {
            for (int j = 0; j < 2 * n - 1; ++j) {
                if ((n + i + j) % 2 == 1) {
                    int x = (j - i + n - 1) / 2;
                    int y = (i + j - n + 1) / 2;
                    if (!ok(x, n) || !ok(y, n)) {
                        continue;
                    }
                    long now = r[i] + l[j] - cost[x][y];
                    if (i % 2 == 0) {
                        if (now > res1) {
                            res1 = now;
                            x1 = x;
                            y1 = y;
                        }
                    } else {
                        if (now > res2) {
                            res2 = now;
                            x2 = x;
                            y2 = y;
                        }
                    }
                }
            }
        }
        out.println(res1 + res2);
        ++x1;
        ++y1;
        ++x2;
        ++y2;
        out.println(x1 + " " + y1 + " " + x2 + " " + y2);
    }

    public void run() {
        try {
            in = new FastReader();
            out = new PrintWriter(System.out);
            solve();
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    public static void main(String[] args) throws IOException {
        new Task().run();
    }
}

class FastReader {
    BufferedReader br;
    StringTokenizer in;

    FastReader() {
        this.br = new BufferedReader(new InputStreamReader(System.in));
    }

    FastReader(String filename) {
        try {
            this.br = new BufferedReader(new FileReader(filename));
        } catch (IOException e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    public String nextToken() throws IOException {
        while (in == null || !in.hasMoreTokens()) {
            in = new StringTokenizer(br.readLine());
        }
        return in.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
}
