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.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.InputMismatchException;

public class GargariAndBishops {

	public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		OutputWriter out = new OutputWriter(System.out);
		int n = in.readInt();
		long ans = 0;
		long arr[][] = new long[n][n];
		long down[][] = new long[n][n];
		long up[][] = new long[n][n];
		int j = 0, i = 0;
		while (j < n) {
			i = 0;
			while (i < n) {
				arr[j][i] = in.readInt();
				i++;
			}
			j++;
		}
		long sum = 0;
		j = 0;
		int k = 0;

		// Down Processing
		while (j < n) {
			k = j;
			i = 0;
			sum = 0;
			while (i < n && k < n) {
				sum += arr[k][i];
				k++;
				i++;
			}
			k = j;
			i = 0;
			while (i < n && k < n) {
				down[k][i] = sum;
				k++;
				i++;
			}
			j++;
		}

		i = 1;
		while (i < n) {
			k = i;
			j = 0;
			sum = 0;
			while (j < n && k < n) {
				sum += arr[j][k];
				k++;
				j++;
			}
			k = i;
			j = 0;
			while (j < n && k < n) {
				down[j][k] = sum;
				k++;
				j++;
			}
			i++;
		}

		// Up Processing
		j = n - 1;
		while (j >= 0) {
			k = j;
			i = 0;
			sum = 0;
			while (i < n && k >= 0) {
				sum += arr[k][i];
				k--;
				i++;
			}
			k = j;
			i = 0;
			while (i < n && k >= 0) {
				up[k][i] = sum;
				k--;
				i++;
			}
			j--;
		}

		i = 1;
		while (i < n) {
			k = i;
			j = n - 1;
			sum = 0;
			while (j >= 0 && k < n) {
				sum += arr[j][k];
				k++;
				j--;
			}
			k = i;
			j = n - 1;
			while (j >= 0 && k < n) {
				up[j][k] = sum;
				k++;
				j--;
			}
			i++;
		}

		// for (int a = 0; a < n; a++) {
		// for (int b = 0; b < n; b++) {
		// System.out.print(up[a][b] + " ");
		// }
		// System.out.println();
		// }
		//
		// for (int a = 0; a < n; a++) {
		// for (int b = 0; b < n; b++) {
		// System.out.print(down[a][b] + " ");
		// }
		// System.out.println();
		// }

		long max = -1;
		int l1 = 0, r1 = 0;
		int l2 = 0, r2 = 0;
		for (int a = 0; a < n; a++) {
			for (int b = 0; b < n; b++) {
				if (up[a][b] + down[a][b] - arr[a][b] > max) {
					max = up[a][b] + down[a][b] - arr[a][b];
					l1 = a;
					r1 = b;
				}
			}
		}
		ans += max;
		max = -1;
		int odd = 0;
		if ((l1 + r1) % 2 == 0) {
			odd = 1;
		}
		for (int a = 0; a < n; a++) {
			for (int b = 0; b < n; b++) {
				if (up[a][b] + down[a][b] - arr[a][b] > max && (a + b) % 2 == odd) {
					max = up[a][b] + down[a][b] - arr[a][b];
					l2 = a;
					r2 = b;
				}
			}
		}
		ans += max;
		System.out.println(ans);
		System.out.println(l1 + 1 + " " + (r1 + 1) + " " + (l2 + 1) + " " + (r2 + 1));
		out.close();
	}

	private static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public long readLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			long sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int readInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public String readString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuffer res = new StringBuffer();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		static boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public String next() {
			return readString();
		}
	}

	private static class OutputWriter {
		private final PrintWriter writer;

		public OutputWriter(OutputStream outputStream) {
			writer = new PrintWriter(outputStream);
		}

		public OutputWriter(Writer writer) {
			this.writer = new PrintWriter(writer);
		}

		public void print(Object... objects) {
			for (int i = 0; i < objects.length; i++) {
				if (i != 0)
					writer.print(' ');
				writer.print(objects[i]);
			}
		}

		public void printLine(Object... objects) {
			print(objects);
			writer.println();
		}

		public void close() {
			writer.close();
		}
	}
}