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.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class GargariAndBishops
{
	static int n;
	static long[] rise;
	static long[] fall;
	
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
 
	static long getrise(int x, int y)
	{
		return rise[x + y];
	}
	static long getfall(int x, int y)
	{
		return fall[n-1-x + y];
	}

	public static void main(String[] args) 
	{
		FastReader sc = new FastReader();
		n = sc.nextInt();
		long[][] a = new long[n][n];
		
		rise = new long[2*n]; //(from the top-left)
		fall = new long[2*n]; //(from the top-right)
		
		long bestodd = -1;
		int x0 = -2;
		int y0 = -2;
		int x1 = -2;
		int y1 = -2;
		long besteven = -1;
		//rise: x + y
		//fall: n-1-x + y

		for(int y = 0; y < n; y++)
		{
			for(int x = 0; x < n; x++)
			{
				a[x][y] = sc.nextInt();
				rise[x+y] += a[x][y];
				fall[n-1-x+y] += a[x][y];
			}
		}

		long r;
		for(int y = 0; y < n; y++)
		{
			for(int x = 0; x < n; x++)
			{
				long pts = rise[x + y] + fall[n-1-x + y] - a[x][y];
				if((x + y)%2 == 0)
				{
					if(pts > besteven)
					{
						besteven = pts;
						x0 = x;
						y0 = y;
					}
				}
				else
				{
					if(pts > bestodd)
					{
						bestodd = pts;
						x1 = x;
						y1 = y;
					}
				}
			}
		}
		r = besteven + bestodd;
		
		System.out.println(r);
		System.out.println((y0+1) + " " + (x0+1) + " " + (y1+1) + " " + (x1+1) + " ");

	}
		

}
