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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.Vector;
 
 
public class Main {
	public static void main(String[] args) throws IOException{
		  	FastScanner sc = new FastScanner();
			PrintWriter out = new PrintWriter(System.out);
			int n =sc.nextInt();
			int a[][]=new int[n][n];
			HashMap<Long,Long>s1 =new HashMap<Long,Long>();
			HashMap<Long,Long>s2 =new HashMap<Long,Long>();

			
			for(long i=0;i<n;i++)
			    for(long j=0;j<n;j++){
				long x =sc.nextLong();
				a[(int) i][(int) j]=(int)x;
				if(s1.containsKey(i+j))s1.put(i+j, s1.get(i+j)+x);
				else
				    s1.put(i+j, x);
				
				if(s2.containsKey(i-j))s2.put(i-j, s2.get(i-j)+x);else s2.put(i-j, x);
			    }
			long max1 =-1; long max2 =-1;int X=0,Y=0; int XX=0;int YY=0;
			for(long i=0;i<n;i++)
			    for(long j=0;j<n;j++){
				long c =s1.get(i+j);
				long cc =s2.get(i-j);
				long ss =c+cc-a[(int) i][(int) j];
				if((i+j) %2==0){
				if(ss>max1){
				    max1=ss;
				    X=(int) (i+1);Y=(int) (j+1);
				}
				}
				else
				    if(ss>max2){
					max2=ss;
					XX=(int) (i+1);YY=(int) (j+1);
				    }
			    }
			
			System.out.println(max1+max2);
			System.out.println(X+" "+Y+" "+XX+" "+YY);
			
						
			System.out.println();
	}
			    
			


			
			
	
	
	

			
	
		
	
	
	
		

			

		

	
	

	
	
	

			
						
			

	
	

		
		
		



	
	
	
	
	
	static void generate(int[] p, int L, int R) {
		  if (L == R) {
			  //the permutation is here ya omar(base case)
		  
		  }else { 
		    for (int i = L; i <= R; i++) {
		    	int tmp = p[L]; p[L] = p[i]; p[i] = tmp;//swap
		      generate(p, L+1, R);//recurse 
		      tmp = p[L]; p[L] = p[i]; p[i] = tmp;//unswap

		    }
		  }
		}
	
}
		 


	
	
	
	











	
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
class FastScanner {
 
 
 
 
    BufferedReader br;
    StringTokenizer st;
 
    public FastScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }
 
    public FastScanner(String s) {
        try {
            br = new BufferedReader(new FileReader(s));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
 
    String nextToken() {
        while (st == null || !st.hasMoreElements()) {
            try {
 
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
 
    int nextInt() {
        return Integer.parseInt(nextToken());
    }
 
    long nextLong() {
        return Long.parseLong(nextToken());
    }
 
    double nextDouble() {
        return Double.parseDouble(nextToken());
    }
 
 
}