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
//package CF;

import java.util.*;
import java.io.*;

public class CF264_C2 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = (n * 2) - 1;
		long[] ri = new long[m];
		long[] le = new long[m];

		int[][] val = new int[n][n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int k = i, h = n - i - 1, lo = 0; lo < n & k < m; h++, lo++, k++) {
				int x = val[i][lo] = Integer.parseInt(st.nextToken());
				ri[k] += x;
				le[h] += x;
			}
		}
		br.close();

		ArrayList<cell> vv = new ArrayList<cell>();

		for (int i = 0; i < n; i++) {
			for (int j = 0, h = n - i - 1; j < n; h++, j++) {
				long v = ri[i + j] + le[h];
				v -= ((long) val[i][j]);
				vv.add(new cell((i * n) + j, v));
			}
		}

		cell xd = new cell(0, new Long("-1"));
		for (int i = 0; i < vv.size(); i++) {
			cell xx = vv.get(i);
			if (xx.val > xd.val) {
				xd = xx;
			}
		}
		
		cell xa = new cell(0, new Long("-1"));

		int x1 = xd.x / n, x2, y1 = xd.x % n, y2;
		for (int i = 0; i < vv.size(); i++) {
			cell xx = vv.get(i);
			if (xx.x != xd.x) {
				x2 = xx.x / n;
				y2 = xx.x % n;
				if ((Math.abs(x1 - x2) + Math.abs(y1 - y2)) % 2 == 1) {
					if (xa.val < xx.val)
						xa = xx;
				}
			}
		}

		System.out.println(xa.val + xd.val);
		System.out.printf("%d %d %d %d\n", (xa.x / n) + 1, (xa.x % n) + 1,
				(xd.x / n) + 1, (xd.x % n) + 1);
	}

	public static class cell implements Comparable<cell> {
		int x;
		Long val;

		public cell(int a, Long v) {
			x = a;
			val = v;
		}

		@Override
		public int compareTo(cell o) {
			if (this.val == o.val)
				return 0;
			return this.val < o.val ? 1 : -1;
		}

	}

}
