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
/**
 * Author   : KillerCage
 * Language : Java
 * Time     : 2014 / 09
 * Quote    : E'la nostra ora incisa sull'anello
 */

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    public static void main( String[] args ) throws IOException {
        InputStream is = System.in;
        OutputStream os = System.out;
        InputReader inr = new InputReader( is );
        PrintWriter out = new PrintWriter( os );

        TaskC KillerCage = new TaskC();
        KillerCage.solve( inr, out );
        out.close();
    }
}

class TaskC {
    InputReader inr;
    PrintWriter out;

    public void solve( InputReader inr, PrintWriter out ) {
        this.inr = inr; this.out = out;
        int n = inr.nextI();
        int[][] a = new int[n][n];
        long[] b = new long[n * 2 - 1];
        long[] c = new long[n * 2 - 1];
        for ( int i = 0; i < n; i ++ ) {
            for ( int j = 0; j < n; j ++ ) {
                a[i][j] = inr.nextI();
                b[i + j] += a[i][j];
                c[i - j + n - 1] += a[i][j];
            }
        }
        long[] max = new long[]{ -1L, -1L };
        int[][] bi = new int[2][2];
        for ( int i = 0; i < n; i ++ ) {
            for ( int j = 0; j < n; j ++ ) {
                int idx = ( i + j ) % 2;
                long value = b[i + j] + c[i - j + n - 1] - a[i][j];
                if ( value > max[idx] ) {
                    max[idx] = value;
                    bi[idx] = new int[]{ i + 1, j + 1 };
                }
            }
        }
        out.printf( "%d\n", max[0] + max[1] );
        out.printf( "%d %d %d %d\n", bi[0][0], bi[0][1], bi[1][0], bi[1][1] );
    }
}

class InputReader {
    private InputStream is;
    int cur_byte_idx = 0;
    int bytes_in_buf = 0;
    byte buf[] = new byte[1024 << 4];

    public InputReader( InputStream is ) {
        this.is = is;
    }

    public int readByte() {
        if ( bytes_in_buf == -1 ) throw new InputMismatchException();
        if ( cur_byte_idx >= bytes_in_buf ) {
            cur_byte_idx = 0;
            try {
                bytes_in_buf = is.read( buf );
            } catch ( IOException e ) {
                throw new InputMismatchException();
            }
            if ( bytes_in_buf <= 0 ) return -1;
        }
        return buf[cur_byte_idx ++];
    }

    public boolean isWhitespace( int c ) {
        return !( c >= 33 && c <= 126 );
    }

    public int skip() {
        int b;
        while ( ( b = readByte() ) != -1 && isWhitespace( b ) ) ;
        return b;
    }

    public Byte nextB() {
        return ( byte ) skip();
    }

    public int nextI() {
    // public long nextL() {
        int b;
        while ( ( b = readByte() ) != -1 && 
            !( ( b >= '0' && b <= '9') || b == '-') );
        int symbol = 1;
        if ( b == '-' ) {
            b = readByte();
            symbol = -1;
        }
        int num = 0;
        // when nextLong: long num = 0;
        while ( true ) {
            if ( b >= '0' && b <= '9' ) {
                num = num * 10 + ( b - '0' );
            } else return symbol * num;
            b = readByte();
        }
    }

    public String next() {
    // public String nextLine() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while ( !isWhitespace( b ) && true ) { // next
        // while ( !isWhitespace(b) || b == ' ') { // nextLine
            sb.appendCodePoint( b );
            b = readByte();
        }
        return sb.toString();
    }

    // public byte[] next( int n ) {
    public byte[] nextLine( int n ) {
        byte[] by = new byte[n];
        int b = skip(), len= 0;
        while ( len < n && !isWhitespace( b ) ) {// next
        // while ( len < n && ( !isWhitespace( b ) || b == ' ' ) ) {// nextLine
            by[len ++] = ( byte ) b;
            b = readByte();
        }
        if ( n == len ) return by;
        return Arrays.copyOf( by, len );
    }

    // public double nextD() {
    //  return Double.parseDouble( next() );
    // }
}
