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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;


public class Main {

   
    
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        long[] F1 = new long[2*n];
        long[] F2 = new long[n+1];//L upper
        long[] F3 = new long[n+1];//L lower
        int[][] a = new int[n][n];
        
        for(int i=0;i<n;i++) {
            String[] in = br.readLine().split(" ");
            for(int j=0;j<n;j++) {
                int x = Integer.parseInt(in[j]);
                a[i][j]=x;
                F1[i+j]+=x;
                if(i < j) {
                    F2[j-i] += x;
                }
                else if(i > j){
                    F3[i-j] += x;
                }
                else{
                    F2[0] += x;
                    F3[0] += x;
                }
            }
        }
        
        long maxA=-1;
        int ia=-1;
        int ja=-1;
        long maxB = -1;
        int ib=-1;
        int jb=-1;
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                long x = F1[i+j];
                x += (i<=j ? F2[j-i] : F3[i-j]);
                //System.out.println("left and right sums "+F1[i+j]+" "+(i<=j ? F2[j-i] : F3[i-j]));
                x-=a[i][j];
                //System.out.println("for "+i+" "+j+" got a total of "+x);
                if( (i+j)%2==0) {
                    
                    if(x > maxA) {
                        maxA = x;
                        ia=i;
                        ja=j;
                    }
                }
                else {
                    if(x > maxB) {
                        maxB = x;
                        ib=i;
                        jb=j;
                    }
                }
            }
        }
        //done
        bw.append(maxA+maxB+"\n");
        bw.append((ia+1)+" "+(ja+1)+" "+(ib+1)+" "+(jb+1)+"\n");
        bw.close();
        
        
    }

    
    

}
