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.awt.List;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;
public class Watermelon2 {
	public static void main(String[] args) throws IOException{
		Main2 m=new Main2();
		m.solve();
	}
	}
class Main2{
	
	 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	 private int[] array;
	    private int[] tempMergArr;
	    private int length;
	
	    BigInteger[] temp=new BigInteger[31];
		BigInteger x,y,z;
	    StringTokenizer stringTokenizer;

	     String next() throws IOException {
	        while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
	            stringTokenizer = new StringTokenizer(reader.readLine());
	        }
	        return stringTokenizer.nextToken();
	    }

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

	    long nextLong() throws IOException {
	        return Long.parseLong(next());
	    }
	    int marr[]=null;
	    void solve() throws IOException  {
	    	      int n=this.nextInt();
	    	     int[][] arr=new int[n][n];
	    	     long[] ipj=new long[n+n];
	    	     long[] imj=new long[n+n];
	    	     for(int i=0;i<n;i++){
	    	    	 for(int j=0;j<n;j++){
	    	    	 arr[i][j]=this.nextInt();
	    	    	 ipj[i+j]+=arr[i][j];
	    	    	 imj[i-j+n]+=arr[i][j];
	    	    	 }
	    	     }
	    	     long max=-1,max0=-1;
	    	     int x=-1,y=-1,x0=-1,y0=-1;
	    	     for(int i=0;i<n;i++){
	    	    	 for(int j=0;j<n;j++){
    	    	//		 System.out.println(xarr[i][j]+" "+max+" "+max0);
	    	    		 long sum=ipj[i+j]+imj[i-j+n]-arr[i][j];
	    	    		 if((i+j)%2==0&&sum>max){
	    	    			 max=sum;
	    	    			 x=i+1;
	    	    			 y=j+1;
	    	    		 }
                         if((i+j)%2==1&&sum>max0){
                        	 max0=sum;
	    	    			 x0=i+1;
	    	    			 y0=j+1;
	    	    			 
	    	    		 }
	    	    	 }
	    	     }
	    	     System.out.println(max+max0);
	    	     System.out.println(x+" "+y+" "+x0+" "+y0);
	    	     
	    }
	    
	    public String recurs(char[] carr,int k){
	    	int count=0;
	    	for(int i=0;i<carr.length;i++){
	    		if(i+k-1<carr.length)
	    		if(carr[i]=='-'){
	    			for(int j=i;j<i+k;j++){
	    				
	    				if(carr[j]=='+')
	    					{carr[j]='-';continue;}
	    				if(carr[j]=='-')
	    					{carr[j]='+';continue;}
	    		//		System.out.println(j+" "+i+" "+carr[j]);
	    			}
	    			count++;
	    			
	    		}
	    	//	display(carr);
	    	}
	    	for(int i=0;i<carr.length;i++){
	    		if(carr[i]=='-')
	    			return "IMPOSSIBLE";
	    	}
	    	return Integer.toString(count);
	    }
	    static int max_LIS=0;
	    public int LIS(int[] arr,int n){
	    	if(n==0)
	    		{
	    		marr[0]=1;
	    		return 1;
	    		}
	    	
	    	int current =1;
	    	for(int i=0;i<n;i++){
	    		int subproblem=0;
	    		if(marr[i]==0)
	    		{
	    			subproblem=LIS(arr,i);
	    			marr[i]=subproblem;
	    		}
	    		else{
	    		//	System.out.println("Hey");
	    			subproblem=marr[i];
	    		}
	    		
	    		System.out.println(current+" "+subproblem+" "+i);
	    		if(arr[i]<arr[n]&&current<(1+subproblem)){
	    			current=(1+subproblem);
	    		}
	    	}
	    	if(max_LIS<current)
	    		max_LIS=current;
	    	return current;
	    }
	    
	public BigInteger comb(int n,int r){
	     x=this.temp[n];
		 y=this.temp[r];
		 z=this.temp[n-r];
	//	 System.out.println(x+" "+y+" "+z);
		 BigInteger ret=x.divide(y.multiply(z));
		 return ret;
		 
	}
	public void fact(){
		this.temp[0]=BigInteger.ONE;
		this.temp[1]=BigInteger.ONE;
		for(int i=2;i<this.temp.length;i++){
			temp[i]=(temp[i-1].multiply(BigInteger.valueOf(i)));
		}
	}
	private static int gcd(int a, int b)
	{
	    while (b > 0)
	    {
	    	int temp = b;
	        b = a % b; // % is remainder
	        a = temp;
	    }
	    return a;
	}
	private static int lcm(int a, int b)
	{
	    return a * (b / gcd(a, b));
	}
	static int[] toFractionPos(int x,int y){
		int a=gcd(x,y);
		int[] arr={x/a,y/a};
		//display(arr);
		return arr;
	}
   
	static void display(long[][] arr){
		
		for(int i=0;i<arr.length;i++){
			for(int j=0;j<arr[i].length;j++){
				System.out.print(arr[i][j]+" ");
		}
		System.out.println();
		}
	System.out.println();
	}

	 static void display(String[] arr){
			for(int i=0;i<arr.length;i++){
				System.out.println(arr[i]+" ");
			}	
			//System.out.println();
		
	 }
	 static void display(long[] arr){
		 for(int i=0;i<arr.length;i++)
				System.out.print(arr[i]+" ");
		System.out.println();
		 }
		 static void display(double[] arr){
		 	   for(int i=0;i<arr.length;i++){
		 		   System.out.print(arr[i]+" ");
		 	   }
		 	   System.out.println();
	    }
	 static void display(char[] arr){
		// System.out.println();
		 int t=0;
			for(int i=0;i<arr.length;i++){
				if(arr[i]!='0'){t=i;break;}
			}	
			while(t!=arr.length){
				System.out.print(arr[t]);
				t++;
			}
			System.out.println();
		
		  }
	 static String str(char[] carr){
		 String str="";
		 for(int i=0;i<carr.length;i++){
			    str=str+carr[i];
			}
		 return str;
	 }
	    public void sort(int inputArr[]) {
	        this.array = inputArr;
	        this.length = inputArr.length;
	        this.tempMergArr = new int[length];
	        doMergeSort(0, length - 1);
	    }
	 
	    private void doMergeSort(int lowerIndex, int higherIndex) {
	         
	        if (lowerIndex < higherIndex) {
	            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
	            // Below step sorts the left side of the array
	            doMergeSort(lowerIndex, middle);
	            // Below step sorts the right side of the array
	            doMergeSort(middle + 1, higherIndex);
	            // Now merge both sides
	            mergeParts(lowerIndex, middle, higherIndex);
	        }
	    }
	 
	    private void mergeParts(int lowerIndex, int middle, int higherIndex) {
	 
	        for (int i = lowerIndex; i <= higherIndex; i++) {
	            tempMergArr[i] = array[i];
	        }
	        int i = lowerIndex;
	        int j = middle + 1;
	        int k = lowerIndex;
	        while (i <= middle && j <= higherIndex) {
	            if (tempMergArr[i] <= tempMergArr[j]) {
	                array[k] = tempMergArr[i];
	                i++;
	            } else {
	                array[k] = tempMergArr[j];
	                j++;
	            }
	            k++;
	        }
	        while (i <= middle) {
	            array[k] = tempMergArr[i];
	            k++;
	            i++;
	        }
	 
	    }
}


 class  Count2 implements Comparable {
    	    Integer i;
    	    Integer j;
    	    Count2(int i,int j){
    	        this.j=j;
    	        this.i=i;
    	    }
    	    void display(){
    	    	System.out.println(i+" "+j);
    	    }
    	    
    	    	@Override
    		public int compareTo(Object o) {
    			// TODO Auto-generated method stub
    			Count2 c=(Count2)o;
    			if(i.compareTo(c.i)>0)
    				return 1;
    			else if(i.compareTo(c.i)<0)
    				return -1;
    			else{
    				return 0;
    				
    			}
    		}
    		
    	}

 class  Counti2 implements Comparable {
    	    Integer i;
    	    Integer j;
    	    Long k;
    	    Counti2(int i,int j,long k){
    	        this.j=j;
    	        this.i=i;
    	        this.k=k;
    	    }
    	    void display(){
    	    	System.out.println(i+" "+j+" "+k);
    	    }
    	    
    	    	@Override
    		public int compareTo(Object o) {
    			// TODO Auto-generated method stub
    			Counti2 c=(Counti2)o;
    			if(k.compareTo(c.k)>0)
    				return 1;
    			else if(k.compareTo(c.k)<0)
    	    		return -1;
    			else
    				return 0;
    		}
    		
    	}

 class  Counti3 implements Comparable {
    	    Integer i;
    	    Integer j;
    	    Integer k;
    	    Integer l;
    	    Long sum;
    	    Counti3(int i,int j,int k,int l,long sum){
    	        this.j=j;
    	        this.i=i;
    	        this.k=k;
    	        this.l=l;
    	        this.sum=sum;
    	    }
    	    void display(){
    	    	System.out.println(i+" "+j+" "+k+" "+l+" "+sum);
    	    }
    	    
    	    	@Override
    		public int compareTo(Object o) {
    			// TODO Auto-generated method stub
    			Counti3 c=(Counti3)o;
    			if(sum.compareTo(c.sum)>0)
    				return 1;
    			else if(sum.compareTo(c.sum)<0)
    	    		return -1;
    			else
    				return 0;
    		}
    		
    	}
		
 class Extra2{
	 ArrayList<Integer> list=new ArrayList<>();
	 Extra2(int i){
		 list.add(i);
	 }
	 void display(){
		 System.out.println(list.size());
		 for(int i=0;i<list.size();i++){
			 System.out.print(list.get(i)+" ");
		 }
		 System.out.println();
	 }
 }