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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.Scanner;

public class Main {

    private InputReader reader;
    private PrintWriter writer;

    Main() {
        reader = new InputReader(System.in);
        writer = new PrintWriter(System.out);
    }

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

    public void run() {

        int n = reader.nextInt();
        long a[][] = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = reader.nextInt();
            }
        }
        long s[][] = new long[n][n];
        long c[][] = new long[n][n];
        long d[][] = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                c[i][j] = d[i][j] = a[i][j];
                if (i > 0 && j > 0) {
                    c[i][j] += c[i - 1][j - 1];
                }
                if (i > 0 && j + 1 < n) {
                    d[i][j] += d[i - 1][j + 1];
                }
            }
        }

        long e[] = new long[n * 2 - 1];
        long f[] = new long[n * 2 - 1];
        for (int i = 0; i < n; i++) {
            e[n - 1 - i + n - 1] = c[n - 1][i];
        }
        for (int i = n - 2; i >= 0; i--) {
            e[i - (n - 1) + n - 1] = c[i][n - 1];
        }

        for (int i = 0; i < n; i++) {
            f[i] = d[i][0];
        }
        for (int i = 1; i < n; i++) {
            f[n - 1 + i] = d[n - 1][i];
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                c[i][j] = e[i - j + n - 1];
                d[i][j] = f[i + j];
            }
        }

        long p = -1;
        int x0 = 0, y0 = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                s[i][j] = c[i][j] + d[i][j] - a[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = (i & 1); j < n; j += 2) {
                if (s[i][j] > p) {
                    p = s[i][j];
                    x0 = i + 1;
                    y0 = j + 1;
                }
            }
        }

        long q = -1;
        int x1 = 0, y1 = 0;
        for (int i = 0; i < n; i++) {
            for (int j = ((i & 1) ^ 1); j < n; j += 2) {
                if (s[i][j] > q) {
                    q = s[i][j];
                    x1 = i + 1;
                    y1 = j + 1;
                }

            }
        }

        System.out.println(p + q);
        System.out.println(x0 + " " + y0 + " " + x1 + " " + y1);
    }

}

class InputReader {
    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int nextChar() {
        if (charCount == -1)
            throw new InputMismatchException();
        if (head >= charCount) {
            head = 0;
            try {
                charCount = stream.read(buffer);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (charCount <= 0)
                return -1;
        }
        return buffer[head++];
    }

    public int nextInt() {
        int c = nextChar();
        while (isSpaceChar(c)) {
            c = nextChar();
        }
        int sign = 1;
        if (c == '-') {
            sign = -1;
            c = nextChar();
        }
        int result = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            result *= 10;
            result += c - '0';
            c = nextChar();
        } while (!isSpaceChar(c));
        return sign * result;
    }

    public boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private InputStream stream;
    private int head, charCount;
    private byte[] buffer = new byte[1024];
}