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.*;
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}

	static class Task {

		static long dp[][], dpr[][], dpl[][], ans[][], max1 = -1, max2 = -1, p1x = 0, p1y = 0, p2x = 0, p2y = 0, st = -1;
		static int n;
		public void solve(int testNumber, InputReader in, OutputWriter out) {
			n = in.nextInt();
			dp = new long[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					dp[i][j] = in.nextInt();
				}
			}
			dpr = new long[n][n];
			dpl = new long[n][n];
			ans = new long[n][n];
			init();
			init2();

			for (int i = 1; i < n; i++) {
				for (int j = 1; j < n - 1; j++) {
					ans[i][j] = funcl(i, j) + funcr(i, j) - dp[i][j];
					check1(ans[i][j], i, j);
				}
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					check2(ans[i][j], i, j);
				}
			}
			out.println(max1 + max2);
			out.println(p1x + " " + p1y + " " + p2x + " " + p2y);
		}
		public long funcl(int i, int j) {
			if (i == j)
				return dpr[0][0];
			else {
				if (i > j)
					return dpr[i - j][0];
				else
					return dpr[0][j - i];
			}
		}
		public long funcr(int i, int j) {
			if (i + j == n - 1)
				return dpl[0][n - 1];
			else {
				if (i + j > n - 1)
					return dpl[i - n + 1 + j][n - 1];
				else
					return dpl[0][i + j];
			}
		}
		public void init() {
			for (int i = 0; i < n; i++) {
				int k = i;
				for (int j = 0; k < n; j++) {
					dpr[i][0] += dp[k++][j];
				}
			}
			for (int j = 1; j < n - 1; j++) {
				int k = j;
				for (int i = 0; k < n; i++) {
					dpr[0][j] += dp[i][k++];
				}
			}
			for (int i = 0; i < n; i++) {
				int k = i;
				for (int j = n - 1; k < n; j--) {
					dpl[i][n - 1] += dp[k++][j];
				}
			}
			for (int j = n - 2; j > 0; j--) {
				int k = j;
				for (int i = 0; k > -1; i++) {
					dpl[0][j] += dp[i][k--];
				}
			}
		}
		public void init2() {
			for (int j = 1; j < n - 1; j++) {
				ans[0][j] = dpl[0][j] + dpr[0][j] - dp[0][j];
				check1(ans[0][j], 0, j);
			}
			for (int i = 0; i < n; i++) {
				ans[i][0] = dpr[i][0];
				check1(ans[i][0], i, 0);
				ans[i][n - 1] = dpl[i][n - 1];
				check1(ans[i][n - 1], i, n - 1);
			}
		}
		public void check1(long val, int i, int j) {
			i++;
			j++;
			if (val > max1) {
				p1x = i;
				p1y = j;
				max1 = val;
				int sum = i + j;
				if (sum % 2 == 0)
					st = 1;
				else
					st = 0;
			}
		}
		public void check2(long val, int i, int j) {
			i++;
			j++;
			int sum = i + j;
			if (st == 1) {
				if (sum % 2 != 0) {
					if (val > max2) {
						p2x = i;
						p2y = j;
						max2 = val;
					}
				}
			} else {
				if (sum % 2 == 0) {
					if (val > max2) {
						p2x = i;
						p2y = j;
						max2 = val;
					}
				}
			}
		}
		public void parr(int arr[][]) {
			System.out.println();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					System.out.print(arr[i][j] + " ");
				}
				System.out.println();
			}
		}
	}

	static class OutputWriter {

		private final PrintWriter writer;

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

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

		public void print(char[] array) {
			writer.print(array);
		}

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

		public void print(int[] array) {
			for (int i = 0; i < array.length; i++) {
				writer.print(array[i]);
			}
		}

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

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

		public void println(int[] array) {
			print(array);
			writer.println();
		}

		public void println(double[] array) {
			print(array);
			writer.println();
		}

		public void println(long[] array) {
			print(array);
			writer.println();
		}

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

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

		public void print(char i) {
			writer.print(i);
		}

		public void println(char i) {
			writer.println(i);
		}

		public void println(char[] array) {
			writer.println(array);
		}

		public void printf(String format, Object... objects) {
			writer.printf(format, objects);
		}

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

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

		public void print(long i) {
			writer.print(i);
		}

		public void println(long i) {
			writer.println(i);
		}

		public void print(int i) {
			writer.print(i);
		}

		public void println(int i) {
			writer.println(i);
		}

		public void separateLines(int[] array) {
			for (int i : array) {
				println(i);
			}
		}

	}

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

		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 int peek() {
			if (numChars == -1) {
				return -1;
			}
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					return -1;
				}
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar];
		}

		public int nextInt() {
			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 long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int 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 String nextString() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				if (Character.isValidCodePoint(c)) {
					res.appendCodePoint(c);
				}
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			if (filter != null) {
				return filter.isSpaceChar(c);
			}
			return isWhitespace(c);
		}

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

		private String readLine0() {
			StringBuilder buf = new StringBuilder();
			int c = read();
			while (c != '\n' && c != -1) {
				if (c != '\r') {
					buf.appendCodePoint(c);
				}
				c = read();
			}
			return buf.toString();
		}

		public String readLine() {
			String s = readLine0();
			while (s.trim().length() == 0) {
				s = readLine0();
			}
			return s;
		}

		public String readLine(boolean ignoreEmptyLines) {
			if (ignoreEmptyLines) {
				return readLine();
			} else {
				return readLine0();
			}
		}

		public BigInteger readBigInteger() {
			try {
				return new BigInteger(nextString());
			} catch (NumberFormatException e) {
				throw new InputMismatchException();
			}
		}

		public char nextCharacter() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			return (char) c;
		}

		public double nextDouble() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.') {
				if (c == 'e' || c == 'E') {
					return res * Math.pow(10, nextInt());
				}
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.') {
				c = read();
				double m = 1;
				while (!isSpaceChar(c)) {
					if (c == 'e' || c == 'E') {
						return res * Math.pow(10, nextInt());
					}
					if (c < '0' || c > '9') {
						throw new InputMismatchException();
					}
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}

		public boolean isExhausted() {
			int value;
			while (isSpaceChar(value = peek()) && value != -1) {
				read();
			}
			return value == -1;
		}

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

		public SpaceCharFilter getFilter() {
			return filter;
		}

		public void setFilter(SpaceCharFilter filter) {
			this.filter = filter;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
		public int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; ++i)array[i] = nextInt();
			return array;
		}
		public int[] nextSortedIntArray(int n) {
			int array[] = nextIntArray(n);
			Arrays.sort(array);
			return array;
		}
		public int[] nextSumIntArray(int n) {
			int[] array = new int[n];
			array[0] = nextInt();
			for (int i = 1; i < n; ++i)array[i] = array[i - 1] + nextInt();
			return array;
		}
		public long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; ++i)array[i] = nextLong();
			return array;
		}
		public long[] nextSumLongArray(int n) {
			long[] array = new long[n];
			array[0] = nextInt();
			for (int i = 1; i < n; ++i)array[i] = array[i - 1] + nextInt();
			return array;
		}
		public long[] nextSortedLongArray(int n) {
			long array[] = nextLongArray(n);
			Arrays.sort(array);
			return array;
		}
	}
}


