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

public class MainC {
	MyScanner sc = new MyScanner();
	Scanner sc2 = new Scanner(System.in);
	final int MOD = 1000000007;
	int[] dx = { 1, -1, -1, 1 };
	int[] dy = { 1, 1, -1, -1 };

	void run() {
		int n = sc.nextInt();
		int[][] f = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				f[i][j] = sc.nextInt();
			}
		}
		long[] left = new long[n * 2 - 1];
		long[] right = new long[n * 2 - 1];
		for (int i = 0; i < n * 2 - 1; i++) {
			int h = i;
			int w = 0;
			if (i >= n) {
				h = n - 1;
				w = i - n + 1;
			}
			while (inner(h, w, n, n)) {
				left[i] += f[h--][w++];
			}
		}
		for (int i = 0; i < n * 2 - 1; i++) {
			int h = i;
			int w = n - 1;
			if (i >= n) {
				h = n - 1;
				w = n * 2 - i - 2;
			}
			while (inner(h, w, n, n)) {
				right[i] += f[h--][w--];
			}
		}
		long[][] p = new long[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				p[i][j] = left[i + j];
				p[i][j] += right[n - j + i - 1];
				p[i][j] -= f[i][j];
			}
		}
		int x1, y1, x2, y2;
		x1 = y1 = x2 = y2 = 0;
		long max1 = -1;
		long max2 = -1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if ((i + j) % 2 == 0) {
					if (p[i][j] > max1) {
						max1 = p[i][j];
						x1 = i + 1;
						y1 = j + 1;
					}
				} else {
					if (p[i][j] > max2) {
						max2 = p[i][j];
						x2 = i + 1;
						y2 = j + 1;
					}
				}
			}
		}
		System.out.println(max1 + max2);
		System.out.println(x1 + " " + y1 + " " + x2 + " " + y2);
	}

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

	void debug2(int[][] array) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				System.out.print(array[i][j]);
			}
			System.out.println();
		}
	}

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	void debug2(long[][] array) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				System.out.print(array[i][j]);
			}
			System.out.println();
		}
	}

	boolean inner(int h, int w, int limH, int limW) {
		return 0 <= h && h < limH && 0 <= w && w < limW;
	}

	class MyScanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-')
					return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		String next() {
			try {
				StringBuilder res = new StringBuilder("");
				int c = System.in.read();
				while (Character.isWhitespace(c))
					c = System.in.read();
				do {
					res.append((char) c);
				} while (!Character.isWhitespace(c = System.in.read()));
				return res.toString();
			} catch (Exception e) {
				return null;
			}
		}
	}
}
