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

public class gargari_bishops 
{
	public long[] scan_sum(int [][] chess, int k, int x1, int y1, int x2, int y2)
	{
		long [] sum = new long [2];
		for (int i = 0; i<= k; i++)
		{
			sum[0] += chess[x1+i][y1+i];
			sum[1] += chess[x2+i][y2+i];
		}
		return(sum);
	}
	
	public long[] scan_sum1(int [][] chess, int k, int x1, int y1, int x2, int y2)
	{
		long [] sum = new long [2];
		for (int i = 0; i<= k; i++)
		{
			sum[0] += chess[x1+i][y1-i];
			sum[1] += chess[x2+i][y2-i];
		}
		return(sum);
	}
	
	static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
 
	
	public static void main(String args[])throws IOException
	{
		Reader sc = new Reader();
		gargari_bishops gb = new gargari_bishops();
		int n = sc.nextInt();
		int [][] chess = new int [n][n];
		for (int i = 0; i< n; i++)
		{
			for (int j = 0; j< n; j++)
			{
				chess[i][j] = sc.nextInt();
			}
		}
		
		long [][] diag1 = new long [n][n];
		long [][] diag2 = new long [n][n];
		
		int k = n-1;
		for (int i = 0; i<n; i++)
		{
			int j =0;
			long [] sum = gb.scan_sum(chess, k, i, 0, 0, i);
			while (j <= k)
			{
				diag1[i+j][0+j] = sum[0];
				diag1[0+j][i+j] = sum[1];
				j++;
			}
			k--;
		}
		k = n-1;
		for (int i = n-1; i >= 0; i--)
		{
			int j =0;
			long [] sum = gb.scan_sum1(chess, k, 0, i, n-1-i, n-1);
			while (j <= k)
			{
				diag2[0+j][i-j] = sum[0];
				diag2[n-1-i+j][n-1-j] = sum[1];
				j++;
			}
			k--;
		}
		
		int xe = 0;
		int ye = 0;
		
		int xo = 0;
		int yo = 1;
		
		long max = diag1[xe][ye] + diag2[xo][yo] + diag2[xe][ye] + diag1[xo][yo] - chess[xo][yo] - chess[xe][ye] ;
		
		for (int i = 1; i<= n; i++)
		{
			for (int j = 1; j<= n; j++)
			{
				if (((i+j)%2 == 0)&&(diag1[i-1][j-1] + diag2[xo][yo] + diag2[i-1][j-1] + diag1[xo][yo] - chess[xo][yo] - chess[i-1][j-1] > max))
				{
					xe = i-1;
					ye = j-1;
					max = diag1[i-1][j-1] + diag2[xo][yo] + diag2[i-1][j-1] + diag1[xo][yo] - chess[xo][yo] - chess[i-1][j-1];
				}
				if (((i+j)%2 != 0)&&(diag1[xe][ye] + diag2[i-1][j-1] + diag2[xe][ye] + diag1[i-1][j-1] - chess[i-1][j-1] - chess[xe][ye] > max))
				{
					xo = i-1;
					yo = j-1;
					max = diag1[xe][ye] + diag2[i-1][j-1] + diag2[xe][ye] + diag1[i-1][j-1] - chess[i-1][j-1] - chess[xe][ye];
				}
			}
		}
		System.out.println(max);
		System.out.println((xe+1)+" "+(ye+1)+" "+(xo+1)+" "+(yo+1));
		
		                                                                                                                                                                                                    
	}

}


