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

public class C_Gargari_and_Bishops{
    public static void main(String[] args) {
        FastScanner s= new FastScanner();
        StringBuilder res = new StringBuilder();
        int n=s.nextInt();
        int matrix[][]= new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                matrix[i][j]=s.nextInt();
            }
        }
        ArrayList<Long> one = new  ArrayList<Long>();
        for(int i=0;i<n;i++){
            long sum=0;
            int p=0;
            for(int j=i;j>=0;j--){
                sum+=matrix[p][j];
                p++;
            }
            one.add(sum);
        }
        for(int i=1;i<n;i++){
            long sum=0;
            int p=n-1;
            for(int j=i;j<n;j++){
                sum+=matrix[j][p];
                p--;
            }
            one.add(sum);
        }
        ArrayList<Long> two = new  ArrayList<Long>();
        for(int i=n-1;i>=0;i--){
            long sum=0;
            int p=0;
            for(int j=i;j<n;j++){
                sum+=matrix[p][j];
                p++;
            }
            two.add(sum);
        }
        for(int i=1;i<n;i++){
            long sum=0;
            int p=0;
            for(int j=i;j<n;j++){
               sum+=matrix[j][p];
               p++;
            }
      two.add(sum);
        }
        long maxodd=Integer.MIN_VALUE;
        long maxeven=Integer.MIN_VALUE;
        int oddx=0;
        int oddy=0;
        int evenx=0;
        int eveny=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if((i+j)%2==0){
                    long sum1=one.get((i+j));
                    int c= Math.min(i,j);
                    int a=i-c;
                    int b=j-c;
                    if(a!=0 && b==0){
                        sum1+=two.get((a+n-1));
                    }
                    else if(b!=0 && a==0){
                         sum1+=two.get((n-b-1));
                    }
                    else if(a==0 & b==0){
                        sum1+=two.get((n-1));
                    }
                    sum1-=matrix[i][j];
                    if(sum1>maxeven){
                        maxeven=sum1;
                        evenx=i;
                        eveny=j;
                    }
                }
                if((i+j)%2!=0){
                    long sum1=one.get((i+j));
                    int c= Math.min(i,j);
                    int a=i-c;
                    int b=j-c;
                    if(a!=0 && b==0){
                        sum1+=two.get((a+n-1));
                    }
                    else if(b!=0 && a==0){
                         sum1+=two.get((n-b-1));
                    }
                    else if(a==0 & b==0){
                        sum1+=two.get((n-1));
                    }
                    sum1-=matrix[i][j];
                    if(sum1>maxodd){
                        maxodd=sum1;
                        oddx=i;
                        oddy=j;
                    }
                }
            }
        }
        System.out.println(maxodd+maxeven);
        oddx++;
        oddy++;
        evenx++;
        eveny++;
       
        System.out.println(evenx+" "+eveny+" "+oddx+" "+oddy);

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