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.*;
import java.util.*;

public class Solution{
    InputStream is;
    static PrintWriter out;
    String INPUT = "";
    static long mod = (long)1e9+7L;
    
    int n, m;
    public void solve(){
        n = ni();
        m=n;
        long ans[][] = new long[n][n];
        long[][] map = new long[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                map[i][j] = nl();
                ans[i][j] = map[i][j];
            }
        }
        for(int i=0; i<n; i++){
            f(i, 0, map, ans);
            g(i, 0, map, ans);
        }
        for(int j=1; j<n; j++){
            f(0, j, map, ans);
            g(n-1, j, map, ans);
        }
        /*
        for(int i=0; i<n; i++){
            long prev = 0;
            for(int j=i, k=0; j<n && k<n; j++, k++){
                ans[j][k]+=prev;
                prev=prev+map[j][k];
            }

            prev=0;
            for(int j=i, k=0; j>=0 && k<n; j--, k++){
                ans[j][k]+=prev;
                prev=prev+map[i][j];
            }

            prev = 0;
        }
        for(int i=1; i<n; i++){
            long prev=0;
            for(int j=i, k=n-1; k>=0 && j<n; k--, j++){
                ans[j][k]+=prev;
                prev+=map[j][k];
            }
        }
        for(int i=0; i<n-1; i++){
            long prev = 0;
            for(int j=i, k=n-1; j>=0 && k>=0; j--, k--){
                ans[j][k]+=prev;
                prev+=map[j][k];
            }
        }*/
/*for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        out.print(ans[i][j]+" ");
    }
    out.println();
}*/

        long white=Long.MIN_VALUE, black=Long.MIN_VALUE;
        int wx=0, wy=0, bx=0, by=0;
        for(int i=0; i<n; i++){
            if(i%2==0){
                for(int j=0; j<n; j+=2){
                    if(white < ans[i][j]){
                        white=ans[i][j];
                        wx=i+1; wy=j+1;
                    }
                }
                for(int j=1; j<n; j+=2){
                    if(black < ans[i][j]){
                        black = ans[i][j];
                        bx=i+1; by=j+1;
                    }
                }
            }
            else{
                for(int j=0; j<n; j+=2){
                    if(black < ans[i][j]){
                        black = ans[i][j];
                        bx=i+1; by=j+1;
                    }
                }
                for(int j=1; j<n; j+=2){
                    if(white < ans[i][j]){
                        white = ans[i][j];
                        wx=i+1; wy=j+1;
                    }
                }
            }
        }
        out.println(white+black);
        out.println(wx+" "+wy+" "+bx+" "+by);
    }
    void f(int x, int y, long[][] map, long[][] ans){
        long s1=0;
        for(int i=x, j=y; i<n && j<n; i++, j++){
            s1=s1+map[i][j];
        }
        for(int i=x, j=y; i<n && j<n; i++, j++){
            ans[i][j]+=s1;
            ans[i][j]-=map[i][j];
        }
    }
    void g(int x, int y, long[][] map, long[][] ans){
        long s1=0;
        for(int i=x, j=y; i>=0 && j<n; i--, j++){
            s1=s1+map[i][j];
        }
        for(int i=x, j=y; i>=0 && j<n; i--, j++){
            ans[i][j]+=s1;
            ans[i][j]-=map[i][j];
        }
    }
    void run(){
        is = new DataInputStream(System.in);
        out = new PrintWriter(System.out);
        int t=1;while(t-->0)solve();
        out.flush();
    }
    public static void main(String[] args)throws Exception{new Solution().run();}
    long mod(long v, long m){if(v<0){long q=(Math.abs(v)+m-1L)/m;v=v+q*m;}return v%m;}
    long mod(long v){if(v<0){long q=(Math.abs(v)+mod-1L)/mod;v=v+q*mod;}return v%mod;}
    //Fast I/O code is copied from uwi code.
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;
    private int readByte(){
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    private String ns(){
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    private char[] ns(int n){
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    private char[][] nm(int n, int m){
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    private int[] na(int n){
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    private int ni(){
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    private long nl(){
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    static  int i(long x){return (int)Math.round(x);}
    static class Pair implements Comparable<Pair>{
        long fs,sc;
        Pair(long a,long b){
            fs=a;sc=b;
        }
        public int compareTo(Pair p){
            if(this.fs>p.fs)return 1;
            else if(this.fs<p.fs)return -1;
            else{
                return i(this.sc-p.sc);
            }
            //return i(this.sc-p.sc);
        }
        public String toString(){
            return "("+fs+","+sc+")";
        }    
    }
    
}