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.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

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

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");

	private void run() throws IOException {
		if (new File("input.txt").exists())
			in = new BufferedReader(new FileReader("input.txt"));
		else
			in = new BufferedReader(new InputStreamReader(System.in));
		if (new File("output.txt").exists())
			out = new PrintWriter("output.txt");
		else
			out = new PrintWriter(System.out);

		solve();

		in.close();
		out.close();
	}

	final int maxn = 2 * 1000 + 10;

	int n;
	int a[][] = new int[maxn][maxn];

	long s[][][] = new long[4][maxn][maxn];
	long summAll[][] = new long[maxn][maxn];

	void solve() throws IOException {
		n = nextInt();
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				a[i][j] = nextInt();

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				if (i > 0 && j > 0)
					s[0][i][j] = s[0][i - 1][j - 1] + a[i - 1][j - 1];
				if (i > 0 && j < n - 1)
					s[1][i][j] = s[1][i - 1][j + 1] + a[i - 1][j + 1];
			}
		for (int i = n - 1; i >= 0; i--)
			for (int j = 0; j < n; j++) {
				if (i < n - 1 && j > 0)
					s[2][i][j] = s[2][i + 1][j - 1] + a[i + 1][j - 1];
				if (i < n - 1 && j < n - 1)
					s[3][i][j] = s[3][i + 1][j + 1] + a[i + 1][j + 1];
			}

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				summAll[i][j] = a[i][j];
				for (int k = 0; k < 4; k++)
					summAll[i][j] += s[k][i][j];
			}

		int x1 = -1, y1 = -1, x2 = -1, y2 = -1;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if ((i + j) % 2 == 0) {
					if (x1 == -1 || (summAll[x1][y1] < summAll[i][j])) {
						x1 = i;
						y1 = j;
					}
				} else {
					if (x2 == -1 || (summAll[x2][y2] < summAll[i][j])) {
						x2 = i;
						y2 = j;
					}
				}

		long ans = summAll[x1][y1] + summAll[x2][y2];
		out.println(ans);
		out.println((x1 + 1) + " " + (y1 + 1) + " " + (x2 + 1) + " " + (y2 + 1));
	}

	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}

	String nextToken() throws IOException {
		while (!st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		return st.nextToken();
	}

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

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

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

	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String str = in.readLine();
			if (str == null)
				return true;
			st = new StringTokenizer(str);
		}
		return false;
	}

}
