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.*;
import java.lang.*;
import java.math.*;


public class cf3 implements Runnable {
	
	long gcd(long a,long b)
    {
    	if(a==0)
    		return b;
    	else
    		return gcd(b%a,a);
    }
	

	 long power(long x, long y, long p)
	    {
	       
	        long res = 1;     
	   
	        x=x % p; 
	     
	        while (y > 0)
	        {
	            
	            if((y & 1)==1)
	                res = ((res%p) * (x%p))% p;
	     
	            y =y >> 1; 
	            x =((x%p)*(x%p))%p; 
	        }
	        return res;
	    }
	 
	
		public void run(){
		
		
		
		InputReader in =  new InputReader(System.in);
		PrintWriter w = new PrintWriter(System.out);
		
		int n=in.nextInt();
		
		long[][] a=new long[n+1][n+1];
		long[][] s1=new long[n+1][n+1];
		long[][] s2=new long[n+2][n+2];
		
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				a[i][j]=in.nextLong();
			}
		}
		
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=n;j++)
			{
				
				if(i+j>=0 && i+j<=n && j+1>=0 && j+1<=n)
					s1[i+j][j+1]+=s1[i+j-1][j] + a[i+j][j+1];
				
			}
		}
		
		for(int i=2;i<=n;i++)
		{
			for(int j=0;j<=n;j++)
			{
				
				if(i+j>=0 && i+j<=n && j+1>=0 && j+1<=n && j+i-1>=0 && j+i-1<=n && j>=0 && j<=n)
					s1[1+j][j+i]+=s1[1+j-1][j+i-1] + a[1+j][j+i];
				
			}
		}
		
	/*	w.println("s1");
	    for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
				w.print(s1[i][j]+" ");
			
			w.println();
		}*/
		
	   // w.println();
		//now s2
	    for(int i=1;i<=n;i++)
		{
			for(int j=n+1;j>=0;j--)
			{
				
				if(i+n+1-j>=0 && i+n+1-j<=n && i+n+1-j-1>=0 && i+n+1-j-1<=n && j-1>=0 && j-1<=n) 
					s2[i+n+1-j][j-1]+=s2[i+n+1-j-1][j] + a[i+n+1-j][j-1];
				
				
			}
		}
		
		for(int i=2;i<=n;i++)
		{
			for(int j=0;j<=n;j++)
			{
				
				if(n+1-i-j>=0 && n+1-i-j<=n && j+1>=0 && j+1<=n && n+1-(j+i-1)>=0 && n+1-(j+i-1)<=n)
					s2[1+j][n+1-j-i]+=s2[1+j-1][n+1-j-i+1] + a[1+j][n+1-j-i];
				
			}
		}
		
	/*	w.println("s2");
	    for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
				w.print(s2[i][j]+" ");
			
			w.println();
		}*/
		
	    
	    long m1=-1;
	    long m2=-1;
	    int p1=0,p2=0,p3=0,p4=0;
	    for(int i=1;i<=n;i++)
	    {
	    	for(int j=1;j<=n;j++)
	    	{
	    		int d=Integer.min(n-i, n-j);
	    		int d1=Integer.min(n-i, j-1);
	    		if((i+j)%2==0)
	    		{
	    			long a1=s1[i+d][j+d] + s2[i+d1][j-d1] - a[i][j];
	    			if(a1>m1)
	    			{
	    				m1=a1;
	    				p1=i;
	    				p2=j;
	    			}
	    		}
	    		else
	    		{
	    			long a2=s1[i+d][j+d] + s2[i+d1][j-d1] - a[i][j];
	    			if(a2>m2)
	    			{
	    				m2=a2;
	    				p3=i;
	    				p4=j;
	    			}
	    		}
	    	}
	    }
	    
	    w.println(m1+m2);
	    w.println(p1+" "+p2+" "+p3+" "+p4);
		w.close();	
		
	}
	
	static class InputReader {
		
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
		
		public InputReader(InputStream stream)
		{
			this.stream = stream;
		}
		
		public int read()
		{
			if (numChars==-1) 
				throw new InputMismatchException();
			
			if (curChar >= numChars)
			{
				curChar = 0;
				try 
				{
					numChars = stream.read(buf);
				}
				catch (IOException e)
				{
					throw new InputMismatchException();
				}
				
				if(numChars <= 0)				
					return -1;
			}
			return buf[curChar++];
		}
	 
		public String nextLine()
		{
			BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
			String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
		}
		public int nextInt()
		{
			int c = read();
			
			while(isSpaceChar(c)) 
				c = read();
			
			int sgn = 1;
			
			if (c == '-') 
			{
				sgn = -1;
				c = read();
			}
			
			int res = 0;
			do 
			{
				if(c<'0'||c>'9') 
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			while (!isSpaceChar(c)); 
			
			return res * sgn;
		}
		
		public long nextLong() 
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') 
			{
				sgn = -1;
				c = read();
			}
			long res = 0;
			
			do 
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			while (!isSpaceChar(c));
				return res * sgn;
		}
		
		public double nextDouble() 
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') 
			{
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.') 
			{
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, nextInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.') 
			{
				c = read();
				double m = 1;
				while (!isSpaceChar(c)) 
				{
					if (c == 'e' || c == 'E')
						return res * Math.pow(10, nextInt());
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}
		
		public String readString() 
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do 
			{
				res.appendCodePoint(c);
				c = read();
			} 
			while (!isSpaceChar(c));
			
			return res.toString();
		}
	 
		public boolean isSpaceChar(int c) 
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	 
		public String next() 
		{
			return readString();
		}
		
		public interface SpaceCharFilter 
		{
			public boolean isSpaceChar(int ch);
		}
	}
    
	public static void main(String args[]) throws Exception
	{
		new Thread(null, new cf3(),"cf3",1<<26).start();
	}
 }   