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.*;
public class Main{
    static long res[];
    static int ans[][];
    public static void main(String args[]) throws IOException{
        BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out);
        int n=Integer.parseInt(sc.readLine().trim());
        res=new long[2];
        ans=new int[2][2];
        res[0]=res[1]=-1;
        long a[][]=new long[n+1][n+1];
        long d1[]=new long[2*n+100];
        long d2[]=new long[2*n+100];
        for(int i=1;i<=n;i++){
            String s[]=sc.readLine().trim().split(" ");
            for(int j=1;j<=n;j++){
                long x=Long.parseLong(s[j-1]);
                a[i][j]=x;
                d1[i+j]+=x;
                d2[i-j+n]+=x;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<n;j++){
                upd((i+j)&1,i,j,d1[i+j]+d2[i-j+n]-a[i][j]);
            }
        }
        pw.println(res[0]+res[1]);
        pw.print(ans[0][0]+" "+ans[0][1]+" ");
        pw.println(ans[1][0]+" "+ans[1][1]);
        pw.flush();
        pw.close();
        sc.close();
    }
    public static void upd(int c,int i,int j,long val){
        if(val>res[c]){
            res[c]=val;
            ans[c][0]=i;
            ans[c][1]=j;
        }
    }
}