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 GargariBishops {
    private static long sum(int r, int c, int[][] grid) {
        long total = grid[r][c];
        int tempR = r;
        int tempC = c;
        /*
        int[] arrayX = new int[] {1,1,-1,-1};
        int[] arrayY = new int[] {1,-1,1,-1};
        for (int x = 0; x < 4; x++) {
            while (true) {
                tempR += arrayX[x];
                tempC += arrayY[x];
                if (tempR >= 0 && tempC >= 0 && tempR < grid.length && tempC < grid.length) {
                    total += grid[tempR][tempC];
                } else {
                    break;
                }
            }
            tempR = r;
            tempC = c;
        }
        */
        return total;
    }
    private static long[] totals1,totals2;
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int quant = Integer.parseInt(in.readLine());
        int[][] grid = new int[quant][quant];
        for (int x = 0; x < quant; x++) {
            StringTokenizer s1 = new StringTokenizer(in.readLine());
            for (int y = 0; y < quant; y++) {
                grid[x][y] = Integer.parseInt(s1.nextToken());
            }
        }
        totals1 = new long[2*quant-1];
        totals2 = new long[2*quant-1];
        for (int x = 0; x < quant; x++) {
            for (int y = 0; y < quant; y++) {
                totals1[x+y] += grid[x][y];
                totals2[x+quant-y-1] += grid[x][y];
            }
        }
        long[][] total = new long[quant][quant];
        for (int x = 0; x < quant; x++) {
            for (int y = 0; y < quant; y++) {
                total[x][y] = totals1[x+y]+totals2[x+quant-y-1]-grid[x][y]; //sum(x,y,grid);
            }
        }
        long maxEven = 0;
        int evenX = -1;
        int evenY = -1;
        long maxOdd = 0;
        int oddX = -1;
        int oddY = -1;
        for (int x = 0; x < quant; x++) {
            for (int y = 0; y < quant; y++) {
                //System.out.println(total[x][y]);
                if ( (x+y) % 2 == 0 && maxEven < total[x][y]) {
                    maxEven = total[x][y];
                    evenX = x;
                    evenY = y;
                } else if ( (x+y) % 2 == 1 && maxOdd < total[x][y]) {
                    maxOdd = total[x][y];
                    oddX = x;
                    oddY = y;
                }
            }
        }
        if(evenX < 0 && evenY < 0) {
            evenX = 0;
            evenY = 0;
        }
        if(oddX < 0 && oddY < 0) {
            oddX = 0;
            oddY = 1;
        }
        System.out.println(maxEven+maxOdd);
        System.out.println((evenX+1) + " " + (evenY+1) + " " + (oddX+1) + " " + (oddY+1));
    }
}