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

public class C {
    
    static BufferedReader in;
    static StringTokenizer t = new StringTokenizer("");

    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(readString());
	long[][] board = new long[n][n];
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
		board[i][j] = Long.parseLong(readString());
	    }
	}
	long[] uprights = new long[2*n];
	long[] downrights = new long[2*n];
	for (int r = 0; r < n; r++) {
	    for (int c = 0; c < n; c++) {
		uprights[r+c] += board[r][c];
		downrights[(n-r-1)+c] += board[r][c];
	    }
	}
	long bestW = 0;
	long bestWR = -1;
	long bestWC = -1;
	long bestB = 0;
	long bestBR = -1;
	long bestBC = -1;
	for (int r = 0; r < n; r++) {
	    for (int c = 0; c < n; c++) {
		long v = uprights[r+c] + downrights[(n-r-1)+c] - board[r][c];
		if ((r+c) % 2 == 0) {
		    if (v >= bestW) {
			bestW = v;
			bestWR = r;
			bestWC = c;
		    }
		} else {
		    if (v >= bestB) {
			bestB = v;
			bestBR = r;
			bestBC = c;
		    }
		}
	    }
	}
	bestWR += 1;
	bestWC += 1;
	bestBR += 1;
	bestBC += 1;
        System.out.println(bestW+bestB);
	System.out.println(bestWR + " " + bestWC + " " + bestBR + " " + bestBC);
    }

    static String readString() throws IOException {
	while (!t.hasMoreTokens()) {
	    t = new StringTokenizer(in.readLine());
	}
	return t.nextToken();
    }

}
