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 c {
public static void main(String[] args) throws IOException
{
    input.init(System.in);
    int n = input.nextInt();
    int[][] data = new int[n][n];
    long[] sumsum = new long[2*n];
    long[] sumdiff = new long[2*n];
    for(int i = 0; i<n; i++)
        for(int j = 0; j<n; j++)
        {
            data[i][j] = input.nextInt();
            sumsum[i+j] += data[i][j];
            sumdiff[i-j+n] += data[i][j];
        }
    Pair maxodd = new Pair(0, 1, -1);
    Pair maxeven = new Pair(0, 0 ,-1);
    for(int i = 0; i<n; i++)
        for(int j = 0; j<n; j++)
        {
            Pair cur = new Pair(i+1, j+1, sumsum[i+j] + sumdiff[i-j+n] - data[i][j]);
            if(cur.compareTo(maxodd) > 0 && (i+j)%2 == 1) maxodd = cur;
            if(cur.compareTo(maxeven) > 0 && (i+j)%2 == 0) maxeven = cur;
        }
    System.out.println(maxodd.val+maxeven.val);
    System.out.println(maxodd.a+" "+maxodd.b+" "+maxeven.a+" "+maxeven.b);
    
}
static class Pair implements Comparable<Pair>
{
    int a, b;
    long val;
    public Pair(int aa, int bb, long vv)
    {
        a = aa; b = bb; val = vv;
    }
    @Override
    public int compareTo(Pair o) {
        // TODO Auto-generated method stub
        return (int)Long.signum(val - o.val);
    }
}
public static class input {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
}
}
