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.*;

public class C {
	FastScanner in = new FastScanner(System.in);
	PrintWriter out = new PrintWriter(System.out);

	public void run() {
		int n = in.nextInt();
		int[][] map = new int[n][];
		for (int i = 0; i < n; i++) map[i] = in.nextIntArray(n);
		
		long[] leftDownSum = new long[2 * n - 1];
		long[] rightDownSum = new long[2 * n - 1];
		
		for (int i = 0; i < n; i++) {
			int x = i, y = 0;
			do {
				leftDownSum[i] += map[y][x];
				
				x--;
				y++;
			} while (x >= 0);
			
			x = n - i - 1; y = 0;
			do {
				rightDownSum[i] += map[y][x];
				
				x++;
				y++;
			} while (x < n);
		}
		
		for (int i = 1; i < n; i++) {
			int x = n - 1, y = i;
			do {
				leftDownSum[n + i - 1] += map[y][x];
				
				x--; y++;
			} while (y < n);
			
			x = 0; y = i;
			do {
				rightDownSum[n + i - 1] += map[y][x];
				
				x++; y++;
			} while (y < n);
		}
		
		long oddRes = Integer.MIN_VALUE, evenRes = Integer.MIN_VALUE;
		int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				long sum = leftDownSum[x + y] + rightDownSum[y + n - x - 1] - map[y][x];
				if ((x + y) % 2 == 0) {
					if (sum > evenRes) {
						x1 = y + 1;
						y1 = x + 1;
						evenRes = sum;
					}
				} else {
					if (sum > oddRes) {
						x2 = y + 1;
						y2 = x + 1;
						oddRes = sum;
					}
				}
			}
		}
		
		System.out.println(evenRes + oddRes);
		System.out.println(x1 + " " + y1 + " " + x2 + " " + y2);
		out.close();
	}

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

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}

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

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

		public FastScanner(InputStream stream) {
			this.stream = stream;
			//stream = new FileInputStream(new File("dec.in"));

		}

		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++];
		}

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

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

		int nextInt() {
			return Integer.parseInt(next());
		}

		int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();

			return array;
		}

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

		long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();

			return array;
		}

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

		double[] nextDoubleArray(int n) {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();

			return array;
		}

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

		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++)
				array[i] = next();

			return array;
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}

