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;



/**
 * The source codes are authored & owned by Rajarshee Mitra (rajarsheem@gmail.com).
 */
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int i,j,n = Integer.parseInt(br.readLine());
        long a[][] = new long[n][n];
        int x1=0,y1=0,x2=0,y2=1;
        long max1=0,max2=0;
        cell c[][] = new cell[n][n];
        
        for(i=0;i<n;i++)
        {
           j=0;           
           String t[] = br.readLine().split(" ");
           while(j<n)           
           {
               a[i][j] = Integer.parseInt(t[j]);
               int x = i, y = j;
               if(x<y)
               {
                   y -= (x-0);
                   x = 0;
               }
               else
               {
                   x -= (y-0);
                   y = 0;
               }
               if(c[x][y]==null)               
                   c[x][y] = new cell();       
               c[x][y].dia1+= a[i][j];
               x= i; y = j;
               if(x-0>n-1-y)
               {
                   x -= (n-1-y);
                   y = n-1;
               }
               else
               {
                   y += (x-0);
                   x = 0;
               }
               if(c[x][y]==null)               
                   c[x][y] = new cell();  
               c[x][y].dia2+= a[i][j];
               
               j++;
               
           }                      
        }
        
        for(i = 0;i<n; i++)
        {           
            for(j=0;j<n; j++)
            {              
                if(c[i][j]==null)                
                    c[i][j] = new cell();    
                
                int x = i, y = j;
               if(x<y)
               {
                   y -= (x-0);
                   x = 0;
               }
               else
               {
                   x -= (y-0);
                   y = 0;
               }
               c[i][j].dia1 = c[x][y].dia1;   
               
               x= i; y = j;
               if(x-0>n-1-y)
               {
                   x -= (n-1-y);
                   y = n-1;
               }
               else
               {
                   y += (x-0);
                   x = 0;
               }
               c[i][j].dia2 = c[x][y].dia2;     
               long t = c[i][j].dia1 + c[i][j].dia2 - a[i][j];
             if((i+j)%2==0 && t>max1)
             {
                 max1 = t; x1 = i; y1 = j ;
             }
             else if((i+j)%2==1 && t>max2)
             {
                 max2 = t; x2 = i; y2 = j;
             }
               
            }
            
        }
        
        
      //  display(a);
    //    display(c);
        System.out.println(max1+max2);
        System.out.println((x1+1)+" "+(y1+1)+" "+(x2+1)+" "+(y2+1));
        
    }
    
    static void display(int a[][])
    {
        for(int i = 0;i<a.length; i++)
        {
            for(int j=0;j<a[0].length; j++)
                System.out.print(a[i][j]+"\t");
            System.out.println();
        }
    }
    static void display(cell a[][])
    {
        for(int i = 0;i<a.length; i++)
        {
            for(int j=0;j<a[0].length; j++)
            {
                if(a[i][j]==null)                
                    a[i][j] = new cell();                
                System.out.print(a[i][j].dia1+","+a[i][j].dia2+"\t");
            }
            System.out.println();
        }
    }
}

class cell
{
    long dia1,dia2;
}