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 Main implements Runnable {
		
	public void solve() throws IOException {
		int N = nextInt();
                int[][] a = new int[N][N];
                for(int i= 0; i < N; i++)
                    for(int j = 0; j < N; j++)
                        a[i][j] = nextInt();
                
                long[] botTop = new long[2 * N];
                long[] topBot = new long[2 * N];
                for(int i = 0; i < N; i++){
                    for(int j = 0; j < N; j++){
                        botTop[i+j] += a[i][j];
                        topBot[i-j+N] += a[i][j];
                    }
                }
                
                long[] bestValue = new long[2];
                Arrays.fill(bestValue, -1);
                int[][] bestIndex = new int[2][];
                for(int i = 0; i < N; i++)
                    for(int j = 0; j < N; j++){
                        int place = (i+j) % 2; //even or odd place
                        long value = botTop[i+j] + topBot[i - j + N] - a[i][j];
                        if(value > bestValue[place]){
                            bestValue[place] = value;
                            bestIndex[place] = new int[]{i+1, j+1};
                        }
                    }
                
                
                System.out.println(bestValue[0] + bestValue[1]);
                System.out.println(bestIndex[0][0] + " " + bestIndex[0][1] + " " + bestIndex[1][0] + " " + bestIndex[1][1]);
	}

	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	//-----------------------------------------------------------
	public static void main(String[] args) {
		new Main().run();
	}

        public void print1Int(int[] a){
                for(int i = 0; i < a.length; i++)
                        System.out.print(a[i] + " ");
                System.out.println();
        }
        
        public void print2Int(int[][] a){
                for(int i = 0; i < a.length; i++){
                        for(int j = 0; j < a[0].length; j++){
                                System.out.print(a[i][j] + " ");
                        }
                        System.out.println();
                }
        }
        
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			tok = null;
			solve();
			in.close();
		} catch (IOException e) {
			System.exit(0);
		}
	}

	public String nextToken() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	BufferedReader in;
	StringTokenizer tok;
}