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 static java.lang.Math.*; 

import java.io.*; 
import java.util.*; 
import java.math.*;

public class Template {
	BufferedReader in; 
	PrintWriter out;
	StringTokenizer st; 

	String next() {
		while (st==null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(in.readLine());
			} catch (Exception e) {}
		}
		return st.nextToken(); 
	}

	int nextInt() {
		return Integer.parseInt(next()); 
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}

	int inf = 1100000000; 


	public void run() throws Exception {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		Long start = System.currentTimeMillis();

			int n = nextInt();

			long[][] a = new long[n][n];
			for (int i=0; i<n; i++)
				for (int j=0; j<n; j++) a[i][j] = nextLong(); 

			long[][] f = new long[n][n]; 
			long[][] g = new long[n][n]; 

			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++) {
					f[i][j]=a[i][j];
					if (i>0 && j+1<n) f[i][j]+=f[i-1][j+1];
				}
			}

			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++) {
					g[i][j]=a[i][j];
					if (i>0 && j-1>=0) g[i][j]+=g[i-1][j-1];
				//	System.err.print(g[i][j] + " "); 
				}
				//System.err.println();
			}

			long[] mx = new long[2];
			long[] x = new long[2];
			long[] y = new long[2];
			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++) {
					int d = min(j, n - i - 1);
					int r = min(n-i-1, n-j-1); 
					long f1 = f[i+d][j-d];
					long f2 = g[i+r][j+r];
					if (mx[(i+j) % 2] <= f1+f2 - a[i][j]) {
						mx[(i+j) % 2] = f1+f2 - a[i][j];
						x[(i+j) % 2] = i;
						y[(i+j) % 2] = j;
					} 
				}	
			}

			out.println(mx[0] + mx[1]);
			out.println((x[0]+1) + " " + (y[0]+1) + " " + (x[1]+1) + " " + (y[1]+1)); 

		out.close(); 
 	}
	
	public static void main(String[] args) throws Exception {
		new Template().run(); 
	}

}