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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class A
{
	static int [][]a;
	static int n;
	static long [][]sum;
	public static boolean isValid(int i,int j)
	{
		return i>=0 && i<n && j>=0 && j<n;
	}
	public static void sumD (int i,int j,int []di,int []dj)
	{
		
		
		for(int k=0;k<di.length;k++)
		{
			long s=0;
			int i2=i;int j2=j;
			while(isValid(i2,j2))
			{
				s+=a[i2][j2];
				i2+=di[k];
				j2+=dj[k];
				
			}
			i2=i;j2=j;
			while(isValid(i2,j2))
			{
				sum[i2][j2]+=s;
				i2+=di[k];
				j2+=dj[k];
				
			}
			//System.out.println(s);
		}
		
		
		/*sum[i][j]-=a[i][j];
		
		for(long []x:sum)
			System.out.println(Arrays.toString(x));*/
		
		
	}
	public static void main(String[] args) throws IOException {
		Scanner sc =new Scanner(System.in);
		n=sc.nextInt();
		a=new int [n][n];
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				a[i][j]=sc.nextInt();
		int []di= {1,-1};
		int []dj= {1,1};
		sum=new long [n][n];
		
		for(int i=0;i<n;i++)
			sumD(i,0,di,dj);
		
		dj[0]=dj[1]=-1;
		for(int i=1;i<n-1;i++)
			sumD(i,n-1,di,dj);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				sum[i][j]-=a[i][j];
		long maxE=0;
		long maxO=0;
		int i1=0,i2=0;
		int j1=0,j2=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				if((i+j)%2==0)
				{	
					if(sum[i][j]>=maxE)
					{
						i1=i;
						j1=j;
					}
					maxE=Math.max(maxE, sum[i][j]);
				}	
				else
				{	
					if(sum[i][j]>=maxO)
					{
						i2=i;j2=j;
					}
					maxO=Math.max(maxO, sum[i][j]);
				}
		i1++;i2++;j1++;j2++;
		System.out.println(maxE+maxO);
		System.out.println(i1+" "+j1+" "+i2+" "+j2);
		
		
		}
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		public Scanner(InputStream s)
		{
			br=new BufferedReader(new InputStreamReader(s));
		}
		public String nextLine() throws IOException
		{
			return br.readLine();
		}
		public String next() throws IOException
		{
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
			
		}
		public double nextDouble() throws IOException
		{
			return Double.parseDouble(next());
		}
		public boolean ready() throws IOException
		{
			return br.ready();
		}
		public long nextLong() throws IOException
		{
			return Long.parseLong(next());
		}
	}
}