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.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;


public class D264_C {

	public static void main(String[] args) throws IOException {
		solve();
	}
	
	static int n;
	static long m[][];
	static long[][] d;
	static long[][] dd;
	
	static void solve() throws IOException {
		BufferedReader in;
		PrintWriter out;
		try {
			in = new BufferedReader(new FileReader("are1231a.in"));
			out = new PrintWriter(new File("are2131a.out"));
		} catch (Exception e) {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(new OutputStreamWriter(System.out));
		}
		StringTokenizer tok = new StringTokenizer(in.readLine());
		n = Integer.valueOf(tok.nextToken());
		m = new long[n][n];
		d = new long[n][n];
		dd = new long[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				d[i][j] = -1L;
				dd[i][j] = -1L;
			}
		}
		for (int i = 0; i < n; i++) {
			tok = new StringTokenizer(in.readLine());
			for (int j = 0; j < n; j++) {
				m[i][j] = Long.valueOf(tok.nextToken());
			}
		}
		
		left();
		right();
		
		
		
		long sum = -1L;
		long sum1 = -1L;
		boolean black = true;
		int x = 0, y = 0, x1 = 0, y1 = 0;
		/*for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(d[i][j]+" ");
			}
			System.out.println();
		}*/
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++, black = !black) {
				if(black) {
					if (sum < d[i][j]) {
						sum = d[i][j];
						x = i+1;
						y = j+1;
					}
				} else {
					if (sum1 < d[i][j]) {
						sum1 = d[i][j];
						x1 = i+1;
						y1 = j+1;
					}
				}
			}
			if (i%2 == 0) black = false; else black = true;
		}
		out.println(sum+sum1);
		out.println(x+" "+y+" "+x1+" "+y1);
		out.close();
		
	}

	
	static void left() {
		long sum = 0L;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (d[i][j] == -1) {
					
					for (int a = i, b = j; a < n && b < n; a++, b++) {
						sum += m[a][b];
					}
					for (int a = i, b = j; a < n && b < n; a++, b++) {
						d[a][b] = sum;
					}
					sum = 0;
				}
			}
		}
		
	}
	
	static void right() {
		long sum = 0L;
		long minus = 0L;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (dd[i][j] == -1) {
					
					for (int a = i, b = j; a < n && b >= 0; a++, b--) {
						sum += m[a][b];
					}
					
					for (int a = i, b = j; a < n && b >= 0; a++, b--) {
						minus = m[a][b];
						dd[a][b] = 1;
						d[a][b] += (sum-minus);
					}
					sum = 0;
				}
			}
		}
	}
}
