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 Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(in, out);
        out.close();
    }
}


class TaskC {

    public void solve(InputReader in, OutputWriter out) {
        int n = in.nextInt();
        int tab[][] = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                tab[i][j] = in.nextInt();
            }
        }
        long firstDiagonals[] = calculateFirstDiagonals(tab,n);
        long secondDiagonals[] = calculateSecondDiagonals(tab, n);

        int j;
        long max = 0;
        int x1=0, y1=0;
        long total = 0;
        for (int i = 0; i < n; i++) {
           if(i % 2 == 0) {
               j = 0;
           } else {
               j = 1;
           }
            while(j < n) {
                long val = calculate(n, firstDiagonals, secondDiagonals, i, j);
                val -= tab[i][j];
                if(val >= max) {
                    max = val;
                    x1 = i;
                    y1 = j;
                }
                j+=2;
            }
        }
        total += max;

        int x2=0, y2=0;
        max = 0;
        for (int i = 0; i < n; i++) {
            if(i%2 == 1) {
                j = 0;
            } else {
                j = 1;
            }
            while(j < n) {
                long val = calculate(n, firstDiagonals, secondDiagonals, i ,j);
                val -= tab[i][j];
                if(val >= max) {
                    max = val;
                    x2 = i;
                    y2 = j;
                }
                j+=2;

            }
        }
        total += max;
        out.printLine(total);
        x1++;
        y1++;
        x2++;
        y2++;
        out.printLine(x1 + " " + y1 + " " + x2 + " " + y2);



    }

    private long calculate(int n, long[] firstDiagonals, long[] secondDiagonals, int i, int j) {
        long sum = 0;
        sum = firstDiagonals[i+j];
        sum += secondDiagonals[n-j+i-1];
        return sum;

    }

    private long[] calculateSecondDiagonals(int[][] tab, int n) {
        long second[] = new long[2*n];
        for(int k=0;k < n; k ++) {
            long sum = 0;
            for (int i = 0; i <= k; i++) {
                sum += tab[i][n-k-1+i];
            }
            second[k] = sum;
        }
        for(int k = n; k < 2* n -1;k++) {
            long sum = 0;
            for (int i = k-n+1; i < n; i++) {
                sum += tab[i][n-k-1+i];
            }
            second[k] = sum;
        }
        return second;
    }

    private long[] calculateFirstDiagonals(int[][] tab, int n) {
        long first[] = new long[2*n];
        for(int k=0;k < n;k++) {
            long sum = 0;
            for (int i = 0; i <= k ; i++) {
                sum += tab[i][k-i];
            }
            first[k] = sum;
        }
        for(int k=n;k < 2*n-1;k++) {
            long sum = 0;
            for (int i = k - n + 1; i < n; i++) {
                sum += tab[i][k-i];
            }
            first[k] = sum;
        }
        return first;
    }
}




class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
    public long nextLong() {
        return Long.parseLong(next());
    }

}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0) {
                writer.print(' ');
            }
            writer.print(objects[i]);
        }
    }

    public void printLine(Object... objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

}