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

public class C {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] cost = new int[n][n];
		for (int r = 0; r < n; r++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int c = 0; c < n; c++) {
				cost[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		long[][] ov = new long[n][n];
		for (int i = 0; i < n; i++) {
			long diag = 0;
			int r = i;
			int c = 0;
			while (r < n) {
				diag += cost[r][c];
				r++;
				c++;
			}
			r = i;
			c = 0;
			while (r < n) {
				ov[r][c] = diag - cost[r][c];
				r++;
				c++;
			}
		}
		for (int i = 1; i < n; i++) {
			long diag = 0;
			int r = 0;
			int c = i;
			while (c < n) {
				diag += cost[r][c];
				r++;
				c++;
			}
			r = 0;
			c = i;
			while (c < n) {
				ov[r][c] = diag - cost[r][c];
				r++;
				c++;
			}
		}
		long maxEven = 0;
		long maxOdd = 0;
		String even = "";
		String odd = "";
		for (int i = 0; i < n; i++) {
			long diag = 0;
			int r = 0;
			int c = i;
			while (c >= 0) {
				diag += cost[r][c];
				r++;
				c--;
			}
			r = 0;
			c = i;
			while (c >= 0) {
				ov[r][c] +=  diag;
				if ((r + c) % 2 == 0) {
					if (ov[r][c] >= maxEven) {
						maxEven = ov[r][c];
						even = (r + 1) + " " + (c + 1);
					}
				} else {
					if (ov[r][c] >= maxOdd) {
						maxOdd = ov[r][c];
						odd = (r + 1) + " " + (c + 1);
					}
				}
				r++;
				c--;
			}
		}
		for (int i = 1; i < n; i++) {
			long diag = 0;
			int r = i;
			int c = n - 1;
			while (r < n) {
				diag += cost[r][c];
				r++;
				c--;
			}
			r = i;
			c = n - 1;
			while (r < n) {
				ov[r][c] +=  diag;
				if ((r + c) % 2 == 0) {
					if (ov[r][c] >= maxEven) {
						maxEven = ov[r][c];
						even = (r + 1) + " " + (c + 1);
					}
				} else {
					if (ov[r][c] >= maxOdd) {
						maxOdd = ov[r][c];
						odd = (r + 1) + " " + (c + 1);
					}
				}
				r++;
				c--;
			}
		}
		System.out.println(maxOdd + maxEven);
		System.out.println(even + " " + odd);
		
	}
	
	public static long hash(int r, int c) {
		return 10000L * r + c;
	}
	
}
