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 Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		long arr[][]=new long[n+2][n+2];
		for(int i=1;i<=n;i++){
			String s=br.readLine();
			String str[]=s.split(" ");
			for(int j=1;j<=n;j++){
				arr[i][j]=Long.parseLong(str[j-1]);
			}
		}

		long dp1[]=new long[3*n+1];
		long dp2[]=new long[3*n+1];
		

		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dp1[i+j]=arr[i][j]+dp1[i+j];
				dp2[i-j+n]=arr[i][j]+dp2[i-j+n];
			}		
		}

		long ans=-1;
		long odd=-1;
		long even=-1;
		int x1=-1;
		int y1=-1;
		int x2=-1;
		int y2=-1;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if((i+j)%2==0){
					long x=dp1[i+j]+dp2[i-j+n]-arr[i][j];
					if(even<x){
						x1=i;
						y1=j;
						even=x;
		
					}
				}else{
					long x=dp1[i+j]+dp2[i-j+n]-arr[i][j];
					if(odd<x){
						x2=i;
						y2=j;
						odd=x;
					}
				}
			}
		}
		System.out.println(even+odd);
		System.out.println(x1+" "+y1+" "+x2+" "+y2);
/*		
		long right[][]=new long[n+2][n+2];
		long left[][]=new long[n+2][n+2];

		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				right[i][j]=right[i-1][j-1]+arr[i][j];
			}
		}

		for(int i=1;i<=n;i++){
			for(int j=n;j>=1;j--){
				left[i][j]=left[i-1][j+1]+arr[i][j];
			}
		}
/*		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				System.out.print(right[i][j]+" ");
			}
			System.out.println();
		}
		long ans=-1;
		int x1=0;
		int x2=0;
		int y1=0;
		int y2=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				int min=Math.min(n-i,n-j);
				long value=right[i+min][j+min];
				min=n-i;
				if(i+j-1<=n){
					value+=left[i+j-1][1];
				}else{
					value+=left[n][j+i-n];
				}
				for(int k=1;k<=n;k++){
					for(int l=1;l<=n;l++){
						if((i+j)%2 != (k+l)%2) {
							min=Math.min(n-k,n-l);
							long value1=right[k+min][l+min];
							if(k+l-1<=n){
								value1+=left[k+l-1][1];
							}else{
								value1+=left[n][k+l-n];
							}
							long tot=value+value1-arr[k][l]-arr[i][j];
							if(tot>ans){
								ans=tot;
								x1=i;
								y1=j;
								x2=k;
								y2=l;
							}
						}
					}
				}
			}
		}
		System.out.println(ans);
		System.out.println(x1+" "+y1+" "+x2+" "+y2);
		*/
	}
}
