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.io.PrintWriter;
import java.util.StringTokenizer;

public class Main
{
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                solve();
            }
        }, "1", 1 << 26).start();
    }
    static void solve () {
        FastReader fr =new FastReader();    PrintWriter op =new PrintWriter(System.out);
        
        int n =fr.nextInt() ,i ,j ,k ,vl[][][] =new int[n+1][n+1][2] ,ans[][] =new int[2][2] ;
        long gd[][] =new long[n+1][n+1] ,dg[][] =new long[2][2*n] ,mo =-1l ,me =-1l ,dm ;
        
        for (i =1 ; i<=n ; ++i) {   for (j =1 ; j<=n ; ++j) gd[i][j] =fr.nextLong() ;    }
        j =n+1 ;  k =1 ;
        for (i =1 ; i<=n ; ++i) {
            int r =--j ,c =k ;
            while ((r<=n) && (c<=n))    {   dg[0][i] += gd[r][c] ;  vl[r][c][0] =i ;  ++r ;   ++c ;   }
        }
        for (; i<2*n ; ++i) {
            int r =j ,c =++k ;
            while ((r<=n) && (c<=n))    {   dg[0][i] += gd[r][c] ;  vl[r][c][0] =i ;  ++r ;   ++c ;   }
        }
        j =n+1 ;    k =n ;
        for (i =1 ; i<=n ; ++i) {
            int r =--j ,c =k ;
            while ((r<=n) && (c>0))    {   dg[1][i] += gd[r][c] ;   vl[r][c][1] =i ;  ++r ;   --c ;   }   
        }
        for (; i<2*n ; ++i) {
            int r =j ,c =--k ;
            while ((r<=n) && (c>0))    {   dg[1][i] += gd[r][c] ;   vl[r][c][1] =i ;  ++r ;   --c ;   }
        }
        //for (i =1; i<2*n; ++i)    System.out.println(dg[0][i]+" "+dg[1][i]) ;
        j =n+1 ;  k =1 ;
        for (i =1 ; i<=n ; ++i) {
            int r =--j ,c =k ;
            while ((r<=n) && (c<=n)) {
                if ((i&1) == 0) {
                    dm =dg[0][vl[r][c][0]] + dg[1][vl[r][c][1]] -gd[r][c] ;
                    if (me < dm)    {   me =dm ;    ans[0][0] =r ;  ans[0][1] =c ;  }
                }
                else {
                    dm =dg[0][vl[r][c][0]] + dg[1][vl[r][c][1]] - gd[r][c] ;
                    if (mo < dm)    {   mo =dm ;    ans[1][0] =r ;  ans[1][1] =c ;  }
                }
                ++r ;   ++c ;
            }
        }
        for (; i<2*n ; ++i) {
            int r =j ,c =++k ;
            while ((r<=n) && (c<=n)) {
                if ((i&1) == 0) {
                    dm =dg[0][vl[r][c][0]] + dg[1][vl[r][c][1]] - gd[r][c] ;
                    if (me < dm)    {   me =dm ;    ans[0][0] =r ;  ans[0][1] =c ;  }
                }
                else {
                    dm =dg[0][vl[r][c][0]] + dg[1][vl[r][c][1]] - gd[r][c] ;
                    if (mo < dm)    {   mo =dm ;    ans[1][0] =r ;  ans[1][1] =c ;  }
                }
                ++r ;   ++c ;
            }
        }
        op.println(me+mo) ; op.println(ans[0][0]+" "+ans[0][1]+" "+ans[1][0]+" "+ans[1][1]) ;
        op.flush();    op.close();
    }
    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();
        }

        String nextLine() {
            String str ="";

            try
            {
                str =br.readLine();
            }
            catch(IOException e)
            {
                e.printStackTrace();
            }

            return str;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next()) ;
        }
    }
}