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.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.io.*;
 
public class GargariBishops {
	
	private static class MyScanner {
	    BufferedReader br;
	    StringTokenizer st;

	    public MyScanner() {
	       br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    String next() {
	        while (st == null || !st.hasMoreElements()) {
	            try {
	                st = new StringTokenizer(br.readLine());
	            } catch (IOException e) {
	                e.printStackTrace();
	            }
	        }
	        return st.nextToken();
	    }

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

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

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

	    String nextLine(){
	        String str = "";
		  try {
		     str = br.readLine();
		  } catch (IOException e) {
		     e.printStackTrace();
		  }
		  return str;
	    }

	 }
	

	
	private static void fill(int x, int y, long[][] arr, long[][] diag, int n, int v, int h)
	{
		
		int i = x;
		int j = y;
		long curr = 0;
		
		curr+=arr[i][j];
	    
		while(valid(i+v,j+h,n))
		  { 
			i = i+v;
			j = j+h;
			curr+=arr[i][j]; 			    
		  }
		
		i = x;
		j = y;
		
		diag[i][j]+=curr;
		 
		while(valid(i+v,j+h,n))
		  { 
			i = i+v;
			j = j+h;
			diag[i][j]+=curr; 			    
		  }
		
	}
	
	
	private static boolean valid(int i, int j, int n)
	{
		return( i>=0 &&i<n && j>=0 && j<n);
	}
	
	public static void solution(long[][] arr, int n)
			
	{	
		long[][] diag = new long[n][n];
		
		for(int t = 0; t<n; t++)
		{
			fill(t,0,arr,diag,n,-1,1);
		}
		
		for(int t = 1; t<n; t++)
		{
			fill(n-1,t,arr,diag,n,-1,1);
		}
		
		for(int t = 0; t<n; t++)
		{
			fill(t,n-1,arr,diag,n,-1,-1);
		}
		
		for(int t = n-2; t>=0; t--)
		{
			fill(n-1,t,arr,diag,n,-1,-1);
		}
		
		long max1 = 0;
		
		int x1 = -1;
		int y1 = -1;
		
		
		for(int i = 0; i<n; i++)
		{
			for(int j = 0; j<n; j++)
			{
				if(x1==-1)
				{
					max1 = diag[i][j]-arr[i][j];
					x1 = i;
					y1 = j;
				}
				
				else
				{
				if(diag[i][j]-arr[i][j]>max1)
				{
					max1 = diag[i][j]-arr[i][j];
					x1 = i;
					y1 = j;
									
				}
				}
				
			}

		}
		
		
		long[][] neigh = new long[n][n];
		long[][] neighl = new long[n][n];
		
		neighl[x1][y1] = 1;
		
		fill(x1,y1,neighl,neighl,n,-1,-1);
		fill(x1,y1,neighl,neighl,n,-1,1);
		fill(x1,y1,neighl,neighl,n,1,-1);
		fill(x1,y1,neighl,neighl,n,1,1);
		
		for(int i = 0; i<n; i++)
		{
			for(int j = 0; j<n; j++)
			{
				if(neighl[i][j]!=0)
				{
					   neigh[i][j] = 1;
								
					  fill(i,j,neigh,neigh,n,-1,-1);
					
					  fill(i,j,neigh,neigh,n,-1,1);
										
					  fill(i,j,neigh,neigh,n,1,-1);
					
					  fill(i,j,neigh,neigh,n,1,1);
					
				}
			}
		}
		
        long max2 = 0;
		
		int x2 = -1;
		int y2 = -1;
		
		for(int i = 0; i<n; i++)
		{
			for(int j = 0; j<n; j++)
			{
				if(neigh[i][j]==0)
				{
					if(x2==-1)
					{
						max2 = diag[i][j]-arr[i][j];
						x2 = i;
						y2 = j;
					}
					
					else
					{
						if (diag[i][j]-arr[i][j]>max2)			 
				        { 
					  max2 = diag[i][j]-arr[i][j];
					  x2 = i;
					  y2 = j;
									
				      }
					}
				}
				
			}

		}
		
		
		out.println(max1+max2);
		out.println((x1+1)+" "+(y1+1)+" "+(x2+1)+" "+(y2+1));
			
		
	}
        
private static PrintWriter out = new PrintWriter(System.out);

public static void main (String[] args)
{
	MyScanner s =  new MyScanner();
     
    int n = s.nextInt();
    long[][] arr = new long[n][n];
    	
    for(int i =0; i<n; i++)
    {	for(int j = 0; j<n; j++)
    		arr[i][j] = s.nextLong();
    }
    	
    solution(arr,n);
    
    out.flush();
    out.close();
    
}
}