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.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author shubh09
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n=in.nextInt();
        long[][] mat=new long[n][n];
        for(int i=0;i<n;i++) for(int j=0;j<n;j++) mat[i][j]=in.nextLong();
        HashMap<Integer,Long> map1=new HashMap<Integer, Long>();
        HashMap<Integer,Long> map2=new HashMap<Integer, Long>();
        for(int s=0;s<=2*(n-1);s++)
        {
            long sum=0;
//            out.println("s="+s);
            for(int i=Math.max(0,s-n+1);i<=Math.min(n-1,s);i++)
            {
                int j=s-i;
                sum+=mat[i][j];
//                out.println("Adding ("+i+","+j+") val="+mat[i][j]);
            }
            map1.put(s,sum);
        }

        for(int d=-n+1;d<n;d++)
        {
            long sum=0;
//            out.println("d="+d);
            for(int i=Math.max(0,d);i<=Math.min(n-1,n-1+d);i++)
            {
                int j=i-d;
                sum+=mat[i][j];
//                out.println("Adding ("+i+","+j+") val="+mat[i][j]);
            }
            map2.put(d,sum);
        }
//        for(Map.Entry<Integer,Long> entry:map2.entrySet()) out.println(entry.getKey()+" "+entry.getValue());
        /*dummyClass elem1=pq1.poll();
        dummyClass elem2=pq1.poll();*/
        long[] max=new long[2];
        int[] x=new int[2];
        x[0]=x[1]=1;
        int[] y=new int[2];
        y[0]=1;y[1]=2;
        for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        {
            int s=i+j,d=i-j;
            mat[i][j]=map1.get(s)+map2.get(d)-mat[i][j];
            int r=s%2;
            if (mat[i][j]>max[r])
            {
                max[r]=mat[i][j];
                x[r]=i+1;y[r]=j+1;
            }
        }
        out.println(max[0]+max[1]);
        out.println(x[0]+" "+y[0]+" "+x[1]+" "+y[1]);
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

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

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

}

