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



/**
 *
 * @author ehab
 */


public class JavaApplication7 {

    /**
     * @param args the command line arguments
     */
    
    
    static long getL(int i , int j )
    {
     int a = i  - 1 ;
     int b = j  - 1 ;
     if(a >= 0 && a < an.length && b >= 0 && b < an.length)
         return an[a][b].s  - an[a][b].r;
     else 
     {     return 0 ;}
     
    
    }
    
    static long getR(int i , int j)
    {
    
     int a = i  - 1 ;
     int b = j  + 1 ;
     if(a >= 0 && a < an.length && b >= 0 && b < an.length)
         return an[a][b].s  - an[a][b].l;
     else 
     { return 0 ;}
     
    }
    static long getD(int i , int j)
    {
    
     int a = i  + 1 ;
     int b = j  - 1 ;
     if(a >= 0 && a < an.length && b >= 0 && b < an.length)
     {return an[a][b].s  - an[a][b].l; }
     else 
     { return an[i][j].s - an[i][j].l  ;}
     
     }
    static long getU(int i , int j)
    {
    
      int a = i  + 1 ;
     int b = j  + 1 ;
     if(a >= 0 && a < an.length && b >= 0 && b < an.length)
         return an[a][b].s  - an[a][b].r;
     else 
     { return an[i][j].s - an[i][j].r  ;}
    
    
    }
    static boolean tk[][] ;
    static void dd(int i , int j)
    {
     for(int q = i , w = j ; q >=0 && w < an.length ; q-- , w++)
     {
      an[q][w].s = -1 ;
     
     }
    for(int q = j , w = i ; q >=0 && w < an.length ; q-- , w++)
    {
     an[w][q].s = -1 ;
    
    
    }
    }
    static void bb(int i , int j){
    
    
     for(int q = i , w = j ; q < an.length  && w < an.length; q++ , w++)
      {  an[q][w].s = -1;
         
      }
       for(int q = i , w = j ; q >= 0  && w >= 0; q-- , w--)
       {
         an[q][w].s = -1;
        
       }
    
    
    }
    static void mak(int i , int j)
    {
      
      for(int q = i , w = j ; q < an.length  && w < an.length; q++ , w++)
      {  an[q][w].s = -1;
         dd(q,w) ;
      }
       for(int q = i , w = j ; q >= 0  && w >= 0; q-- , w--)
       {
         an[q][w].s = -1;
         dd(q,w) ;
       }
       
     for(int q = i , w = j ; q >=0 && w < an.length ; q-- , w++)
     {
      an[q][w].s = -1 ;
      bb(q,w) ;
     }
    for(int q = j , w = i ; q >=0 && w < an.length ; q-- , w++)
    {
     an[w][q].s = -1 ;
      bb(w,q) ;
    
    }
       
    }
    static  pair an[][] ;
    public static void main(String[] args) throws Exception 
    {
      
        StringBuilder ans = new StringBuilder();
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)) ;
        StringTokenizer st = new StringTokenizer(bf.readLine()) ; 
        int a = Integer.parseInt(st.nextToken()) ;
      
        an = new pair[a][a] ;
        for(int i = 0 ; i < a ; i++){
            st = new StringTokenizer(bf.readLine()) ; 
            for(int j = 0 ; j < a ; j++)
                an[i][j] = new pair(0,0,Integer.parseInt(st.nextToken())) ;}
        for(int i = 0 ; i < a ; i++)
            for(int j = 0 ; j < a ; j++)
            {
              an[i][j].l = getL(i,j)  ;
              an[i][j].r = getR(i,j)  ;
              an[i][j].s += an[i][j].l +  an[i][j].r ;
               
            }
         for(int i = a - 1 ; i >= 0 ; i--)
            for(int j = a- 1 ; j >=  0; j--)
            {
            
             
              long b = an[i][j].s -(an[i][j].l+an[i][j].r) ;
              long x = getU(i, j) ;
              long z = getD(i, j) ;
              an[i][j].s = x +  z - b ;
              an[i][j].l = x - b ;
              an[i][j].r = z - b ;
            
            }
        long max = 0 ; 
        int r = -1 ; int t = -1 ;
    for(int i = 0 ; i < a ; i++)
    { for(int j = 0 ; j < a ; j++)
              if(an[i][j].s >= max)
              {
               max = an[i][j].s ;
               r = i ; t = j ;
              
              }
     
    }
    mak(r,t) ;
    long aw = max ;
    ans.append((r+1)+" " + (t+1)+" ") ;
    max = 0 ;
     for(int i = 0 ; i < a ; i++)
    { for(int j = 0 ; j < a ; j++)
              if(an[i][j].s >= max)
              {
               max = an[i][j].s ;
               r = i ; t = j ;
              
              }
     
    }
     aw += max ;
     ans.append((r+1)+" " + (t+1)) ;
        System.out.println(aw);
        System.out.println(ans);
    }
}
class pair {
long l , r ;
long s = 0 ;
pair(long a,long b , long w ){
l = a;
r = b ;
s = w ;
}


}