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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class ProblemC {
	private static BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
	private static StringTokenizer st = new StringTokenizer("");
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		int n = nextInt();
		int nMinusOne = n-1;
		long[] diagonalsR = new long[2*n];
		long[] diagonalsL = new long[2*n];
		int[][] board = new int[n][n];
		for (int x = 0; x < n; x++) {
			for (int y = 0; y < n; y++) {
				int cell = nextInt();
				board[x][y] = cell;
				diagonalsR[nMinusOne+(y-x)] += cell;
				diagonalsL[x+y] += cell;
			}
		}
	
		long max1, x1, y1;
		long max2, x2, y2;
		max1 = max2 = x1 = x2 = y1 = y2 = -1;
		long value = 0;
		for (int x = 0; x < n; x++) {
			int diagL = x;
			int diagR = nMinusOne-x;
			boolean white = (x % 2) == 0;
			for (int y = 0; y < n; y++) {
				value = diagonalsR[diagR] + diagonalsL[diagL] - board[x][y];
				if (white) {
					if (value > max1) {
						x1 = x;
						y1 = y;
						max1 = value;
					}
				} else if (value > max2) {
					max2 = value;
					x2 = x;
					y2 = y;
				}
				diagL++;
				diagR++;
				white = !white;
			}
		}
		
		System.out.println(max1+max2);
		System.out.println((x1+1) + " " + (y1+1) + " " + (x2+1) + " " + (y2+1)); 
	}
	
	private static String nextString() throws IOException {
		while(!st.hasMoreTokens())
			st = new StringTokenizer(stdin.readLine());
		return st.nextToken();
	}
	private static int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(nextString());
	}
}
