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.util.*;import java.io.*;import java.math.*;
public class Main
{
    public static void process()throws IOException
    {
        int n=ni();
        long[][]A=new long[n][n];
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                A[i][j]=nl();
        int[][]fl=new int[n][n];
        int[][]fr=new int[n][n];
        ArrayList<Long>left = new ArrayList<>();
        ArrayList<Long>right = new ArrayList<>();
        for(int i=n-1;i>=0;i--)
        {
            long temp=0;
            for(int j=0;j<n;j++)
            {
                if(i+j>=n)
                    break;
                temp+=A[i+j][j];
                fl[i+j][j]=left.size();
            }
            left.add(temp);
        }
        for(int i=1;i<n;i++)
        {
            long temp=0;
            for(int j=i;j<n;j++)
            {
                temp+=A[j-i][j];
                fl[j-i][j]=left.size();
            }
            left.add(temp);
        }
        for(int i=n-1;i>=0;i--)
        {
            long temp=0;
            int c=i;
            for(int j=n-1;j>=0;j--)
            {
                if(c>=n)
                    break;
                temp+=A[c][j];
                fr[c][j]=right.size();
                c++;
            }
            right.add(temp);
        }
        for(int i=n-2;i>=0;i--)
        {
            long temp=0;
            int c=0;
            for(int j=i;j>=0;j--)
            {
                temp+=A[c][j];
                fr[c][j]=right.size();
                c++;
            }
            right.add(temp);
        }
        long m1=-1l,m2=-1l;
        int x1=0,x2=0,y1=0,y2=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                long temp=left.get(fl[i][j])+right.get(fr[i][j])-A[i][j];
                if((i+j)%2==0)
                {
                    if(m1<temp)
                    {
                        m1=temp;
                        x1=i+1;
                        y1=j+1;
                    }
                }
                else
                {
                    if(m2<temp)
                    {
                        m2=temp;
                        x2=i+1;
                        y2=j+1;
                    }
                }
            }
        }
        pn(m1+m2);
        pn(x1+" "+y1+" "+x2+" "+y2);            
    }

    static AnotherReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        boolean oj = System.getProperty("ONLINE_JUDGE") != null;
        if(oj){sc=new AnotherReader();out=new PrintWriter(System.out);}
        else{sc=new AnotherReader(100);out=new PrintWriter("output.txt");}
        int t=1;
        // t=ni();
        while(t-->0) {process();}
        out.flush();out.close();  
    }

    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static void pni(Object o){out.println(o);out.flush();}
    static int ni()throws IOException{return sc.nextInt();}
    static long nl()throws IOException{return sc.nextLong();}
    static double nd()throws IOException{return sc.nextDouble();}
    static String nln()throws IOException{return sc.nextLine();}
    static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
    static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}

/////////////////////////////////////////////////////////////////////////////////////////////////////////

    static class AnotherReader{BufferedReader br; StringTokenizer st;
    AnotherReader()throws FileNotFoundException{
    br=new BufferedReader(new InputStreamReader(System.in));}
    AnotherReader(int a)throws FileNotFoundException{
    br = new BufferedReader(new FileReader("input.txt"));}
    String next()throws IOException{
    while (st == null || !st.hasMoreElements()) {try{
    st = new StringTokenizer(br.readLine());}
    catch (IOException  e){ e.printStackTrace(); }}
    return st.nextToken(); } int nextInt() throws IOException{
    return Integer.parseInt(next());}
    long nextLong() throws IOException
    {return Long.parseLong(next());}
    double nextDouble()throws IOException { return Double.parseDouble(next()); }
    String nextLine() throws IOException{ String str = ""; try{
    str = br.readLine();} catch (IOException e){
    e.printStackTrace();} return str;}}
   
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}