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.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class CodeForces {
    static reader input = new reader();
    static PrintWriter output = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {
        /*
        BufferedReader bf = new BufferedReader(new FileReader("input.txt"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
        StringTokenizer stk= new StringTokenizer(bf.readLine());;
        int n=Integer.parseInt(stk.nextToken());
        */
        C();
        output.close();
    }

    public static void A(){

    }

    public static void B(){

    }

    public static void C(){
        int n=input.nextInt();
        int mat[][]=new int[n][n];
        for(int i=0;i<n;i++) {
            for (int j = 0; j < n; j++) {
                mat[i][j] = input.nextInt();
            }
        }
        HashMap<Integer,Long>primary=new HashMap<>();
        HashMap<Integer,Long>secondary=new HashMap<>();
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                primary.put(j-k,primary.getOrDefault(j-k,0l)+mat[j][k]);
                secondary.put(j+k,secondary.getOrDefault(j+k,0l)+mat[j][k]);
            }
        }
        long odd=-1,even=-1;
        int oddx=-1,oddy=-1,evenx=-1,eveny=-1;
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                long temp=primary.get(j-k)+secondary.get(j+k)-mat[j][k];
                if((j+k)%2==1){
                    if(odd<temp){
                        odd=temp;
                        oddx=j;
                        oddy=k;
                    }
                }else{
                    if(even<temp){
                        even=temp;
                        evenx=j;
                        eveny=k;
                    }
                }
            }
        }

        oddx++;oddy++;evenx++;eveny++;
        output.println(odd+even);
        output.println(oddx+" "+oddy+" "+evenx+" "+eveny);

    }

    public static void D(){

    }

    public static void E(){

    }

    public static void F(){

    }

    public static long factorial(int a){
        long ans=1;
        for(int i=1;i<=a;i++){
            ans*=i;
        }
        return ans;
    }
    public static long LCM(long a,long b){
        return (a*b)/GCD(a,b);
    }
    public static long GCD(long a,long b){
        if(a==0)
            return b;
        else if(b==0)
            return a;
        else
            return GCD(b%a,a);
    }

    public static boolean isPrime(long num){
        if(num==1)
            return false;
        else if(num==2||num==3)
            return true;
        else if(num%2==0||num%3==0)
            return false;
        else{
            for(long i=5;i*i<=num;i+=6){
                if(num%i==0||num%(i+2)==0)
                    return false;
            }
        }
        return true;
    }

    public static ArrayList<Integer> SieveofEratothenis(){
        ArrayList<Integer>ans=new ArrayList<>();
        boolean visited[]=new boolean[1000000];
        for(int i=2;i<1000000;i++){
            if(!visited[i]){
                ans.add(i);
                for(long j=(long)i*i;j<1000000;j+=i){
                    visited[(int)j]=true;
                }
            }
        }
        return ans;
    }

    public static void mergesort(long arr[],int start,int end){//start and end must be indexes
        if(start<end) {
            int mid=(start+end)/2;
            mergesort(arr,start,mid);
            mergesort(arr, mid+1, end);
            merge(arr, start,mid,end);
        }
    }
    public static void merge(long arr[],int start,int mid,int end){
        int lsize=mid-start+1,rsize=end-mid;
        long l[]=new long[lsize],r[]=new long[rsize];
        for(int i=start;i<=mid;i++){
            l[i-start]=arr[i];
        }
        for(int i=mid+1;i<=end;i++){
            r[i-mid-1]=arr[i];
        }
        int i=0,j=0,k=start;
        while(i<lsize&&j<rsize){
            if(l[i]<=r[j]){
                arr[k++]=l[i++];
            }else{
                arr[k++]=r[j++];
            }
        }
        while(i<lsize)
            arr[k++]=l[i++];
        while(j<rsize)
            arr[k++]=r[j++];
    }
}

class Value{
    int ans;
}

class Pair{
    int x,y;
    Pair(int x,int y){
        this.x=x;
        this.y=y;
    }
}

class Op{
    int op,count;
    char dir;
    public Op(int op){
        this.op=op;
    }
}

class reader {
    BufferedReader br;
    StringTokenizer st;

    public reader() {
        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();
    }

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

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

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }

    public int[] nextIntArray(int arraySize) {
        int array[] = new int[arraySize];
        for (int i = 0; i < arraySize; i++) {
            array[i] = nextInt();
        }
        return array;
    }

    public long[] nextLongArray(int arraySize) {
        long array[] = new long[arraySize];
        for (int i = 0; i < arraySize; i++) {
            array[i] = nextLong();
        }
        return array;
    }
}
