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


public class c463 {

	public static void main(String[] args)throws IOException {
		
		BufferedReader ds = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(ds.readLine());
		
		long prim[] = new long[n*2];
		
		long secon[] = new long[n*2];
		
		long a[][] = new long[n][n];
		
		StringTokenizer st;
		
		for(int i = 0 ; i < n ; i++)
		{
			st = new StringTokenizer(ds.readLine());
			
			for(int j = 0 ; j < n  ;j++)
			{
				a[i][j] = Integer.parseInt(st.nextToken());
			
				prim[i+j] += a[i][j];
				
				secon[n+i-j-1] += a[i][j];
			}
		}
		
		long max[] = new long[2];
		
		max[0] = max[1] = -1;
		
		int i1[] = new int[2];
		int j1[] = new int[2];
		
		for(int i = 0 ; i < n ; i++)
		{			
			for(int j = 0 ; j < n ; j++)
			{
				long x = prim[i+j]+secon[n+i-j-1]-a[i][j];
				
				int pos = (i+j)%2;
				
				if(max[pos] < x)
				{
					max[pos] = x;
					i1[pos] = i;
					j1[pos] = j;
				}
				
			}
		}
		

		i1[0]++;i1[1]++;j1[0]++;j1[1]++;
		
		PrintWriter out = new PrintWriter(System.out);
		
		out.println(max[0]+max[1]+"\n"+i1[1]+" "+j1[1]+" "+i1[0]+" "+j1[0]);
		
		out.close();
		
	}

}
