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.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class Main{
	
	// ArrayList<Integer> lis = new ArrayList<Integer>();
	// ArrayList<String> lis = new ArrayList<String>();
	//  PriorityQueue<P> que = new PriorityQueue<P>();
	// PriorityQueue<Integer> que = new PriorityQueue<Integer>();
	//  Stack<Integer> que = new Stack<Integer>();
    //	static long sum=0;
	// 1000000007 (10^9+7)
	static int mod = 1000000007;
	//static int mod = 1000000009,r=0; ArrayList<Integer> l[]= new ArrayList[n];
   // static int dx[]={1,-1,0,0};
//	static int dy[]={0,0,1,-1};
//	static int dx[]={1,-1,0,0,1,1,-1,-1};
//  static int dy[]={0,0,1,-1,1,-1,1,-1};
	//static Set<Integer> set = new HashSet<Integer>();p
	
public  static void main(String[] args)   throws Exception, IOException{
   //String line=""; throws Exception, IOException
   //(line=br.readLine())!=null
	//Scanner sc =new Scanner(System.in);
	// !!caution!! int long //  
	Reader sc = new Reader(System.in);


 //,a=sc.nextInt(),b=sc.nextInt();
 	// int n=sc.nextInt(),p[]=new int[n],q[]=new int[n];
	//int n=sc.nextInt(),a[]=new int[n],b[]=new int[n];
 

	 int n=sc.nextInt(),b[][]=new int[n+3][n+3];
	 
		   for(int i=0;i<n;i++){
                for (int j = 0; j <n; j++) {

                	 b[i+1][j+1]=sc.nextInt();

				}

			   
		   }
        
		   long e[][]=new long[2*n+2][2],r=0;
		   

		   for(int i=1;i<=n;i++){
			   int x=1,y=i;
			   while( y>0 ){
				   e[i][0]+=b[x][y];
				   y--;x++;
			   }
		   }
		   
		   for(int i=2;i<=n;i++){
			   int x=i,y=n;
			   while( x<=n ){
				   e[i+n-1][0]+=b[x][y];
				   y--;x++;
			   }
		   }
		   
		   for(int i=n; 1<=i ;i--){
			   int x=1,y=i;
			   while( y<=n ){
				   e[n-i+1][1]+=b[x][y];
				   y++;x++;
			   }
		   }
		   for(int i=2; i<=n ;i++){
			   int x=i,y=1;
			   while( x<=n ){
				   e[n+i-1][1]+=b[x][y];
				   y++;x++;
			   }
		   }
		//    db(e);
		   
		  
		   ArrayList<P> lis = new ArrayList<P>();
		   
		   for(int i=1;i<=n;i++){
			   for(int t=1;t<=n;t++){
				    int a=i+t-1,c= abs(i-1)+abs(t-n)+1 ;
			long tt=e[a][0]+e[c][1]-b[i][t];
		//	db(tt);
			lis.add(new P(i,t,tt));
				  
			   }
		   } 
		   
		   boolean mm[][]=new boolean[n+2][n+2];
		   
		   sort(lis);
		  // db(lis.get(0),lis.get(1));
		   P p=null,q=null; long m=-1;
		   for(int i=0;i<lis.size();i++){
			  // db(lis.get(i).d,lis.get(i).x,lis.get(i).y);
			   P k=lis.get(i);
			   if( 2*k.d<=m )break;
			   boolean bd[][]=new boolean[n+2][n+2];
			   long z=k.d;
			   
			   int x=k.x,y=k.y;
			   
			   while( x<=n && 1<=x &&  y<=n && 1<=y){bd[x][y]=true; x++; y++;  } x=k.x;y=k.y;
			   while( x<=n && 1<=x &&  y<=n && 1<=y){bd[x][y]=true; x--; y++;  } x=k.x;y=k.y;
			   while( x<=n && 1<=x &&  y<=n && 1<=y){bd[x][y]=true; x++; y--;  } x=k.x;y=k.y;
			   while( x<=n && 1<=x &&  y<=n && 1<=y){bd[x][y]=true; x--; y--;  } 
			   
			   
			   
			   
			 lp: for(int t=i+1;t<lis.size();t++){
				   P l=lis.get(t);
				   if( m>z+l.d )break;
				   x=l.x;y=l.y;
				   if( mm[x][y] )continue;
				   while( x<=n && 1<=x &&  y<=n && 1<=y){if(bd[x][y])continue lp; x++; y++;  }  x=l.x;y=l.y;
				   while( x<=n && 1<=x &&  y<=n && 1<=y){if(bd[x][y])continue lp; x--; y++;  }   x=l.x;y=l.y;
				   while( x<=n && 1<=x &&  y<=n && 1<=y){if(bd[x][y])continue lp; x++; y--;  }  x=l.x;y=l.y;
				   while( x<=n && 1<=x &&  y<=n && 1<=y){if(bd[x][y])continue lp;x--; y--;  }   
				   
				   if( !bd[l.x][l.y] ){  z+=l.d;  if( m<z ){ m=z; p=k; q=l; } break;  }
			   }x=k.x;y=k.y;
			     mm[x][y] = true;
		   }
		 
		   System.out.println(m);
		   System.out.println(p.x+" "+p.y+" "+q.x+" "+q.y);
		 //  System.out.println(r);

}





static void db(Object... os){
    System.err.println(Arrays.deepToString(os));

}

}


 
class P implements Comparable<P>{
//	implements Comparable<Pair>
	int x,y; long d;
	P(int x,int y,long d){
		this.x=x;
		this.y=y;
		this.d=d;
	} 
	public int compareTo(P x){
		if( x.d==d )return 0;
		 return  (int)(x.d-d>=0 ?1:-1) ; //ascend
	   }
 
}

 /*
    class P implements Comparable<P>{
//		implements Comparable<Pair>
		int id; long d;
		P(int id,long d){
			this.id=id;
			this.d=d;
		} 
		public int compareTo(P x){
			 return  0<d-x.d ? 1:0 ; //descend
		   }
	 
 }

  /*

class Pair implements Comparable<Pair>{
//	implements Comparable<Pair>
	int a,b;
	Pair(int a,int b){
		this.a=a;
		this.b=b;
	} 
	public int compareTo(Pair x){
	   	 return a-x.a; //descend
	   }
}*/

class Reader
{ 
	private BufferedReader x;
	private StringTokenizer st;
	
	public Reader(InputStream in)
	{
		x = new BufferedReader(new InputStreamReader(in));
		st = null;
	}
	public String nextString() throws IOException
	{
		while( st==null || !st.hasMoreTokens() )
			st = new StringTokenizer(x.readLine());
		return st.nextToken();
	}
	public int nextInt() throws IOException
	{
		return Integer.parseInt(nextString());
	}
	public long nextLong() throws IOException
	{
		return Long.parseLong(nextString());
	}
	public double nextDouble() throws IOException
	{
		return Double.parseDouble(nextString());
	}
}
