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.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;


public class C {

	final static int MAX = 2001;
	static int size;
	
	int [][] board = new int [MAX][MAX];
	
	public static void main(String[] args) {
		
		C test = new C();
		
//		test.size = 4;
//		if ( test.getUp(new Loc(2,3)) != 6 )
//			throw new RuntimeException();
//		if ( test.getDown(new Loc(2,3)) != 5 )
//			throw new RuntimeException();
		
		try {
			test.solve();
		} catch (NumberFormatException | IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	public void solve() throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader( new InputStreamReader(System.in) );
		size = Integer.parseInt(bf.readLine());
		
		ArrayList<Loc> blacks = new ArrayList<Loc>();
		ArrayList<Loc> whites = new ArrayList<Loc>();
		
		// read board, and
		// sort black and white locations
		for (int i = 0; i < size; ++i) {
			String line = bf.readLine();
			int j = 0;
			for (String numStr: line.split(" ")) {
				board[i][j] = Integer.parseInt(numStr);
				if ((i+j) % 2 == 0)
					blacks.add(new Loc(i, j));
				else
					whites.add(new Loc(i, j));
				j++;
			}
		}

		// now find the sums over diagonals
		
		// first \
		long [] down = new long [size*2];
		// top-right is size, goes from 1 ... size .. 2*size-1
		for (int i = 1; i < 2*size; ++i) {
			// find corresponding loc
			Loc start = null;
			int ahh = i;
			if (i < size) {
				start = new Loc(0, size - ahh);
			} else {
				start = new Loc(ahh - size, 0);
			}
			down[2*size - i] = countRew(start, new Loc(+1, +1));
		}
		
		// second /
		long [] up = new long [size*2];
		// bottom-right is size, goes from 1 ... size .. 2*size-1
		for (int i = 1; i < 2*size; ++i) {
			// find corresponding loc
			Loc start = null;
			if (i < size) {
				start = new Loc(i-1, 0);
			} else {
				start = new Loc(size-1, i-size);
			}
			up[i] = countRew(start, new Loc(-1, +1));
		}

		// now find best place
		long bestRewB = -1, bestRewW = -1;
		Loc bestBlack = null, bestWhite = null;
		for (Loc b : blacks) {
			long bd = down[getDown(b)];
			long bu = up[getUp(b)];
			long rew = bd + bu - board[b.i][b.j];
			if (rew > bestRewB) {
				bestRewB = rew;
				bestBlack = b;
			}
		}
		for (Loc w : whites) {
			long wd = down[getDown(w)];
			long wu = up[getUp(w)];
			long rew = wd + wu - board[w.i][w.j];
			if (rew > bestRewW) {
				bestRewW = rew;
				bestWhite = w;
			}
		}
		
		System.out.println(bestRewB + bestRewW);
		System.out.println(bestBlack + " " + bestWhite);
	}

	int getDown(Loc l) {
		// first go ..
		int i = l.i;
		int j = l.j;
		int m = Math.min(i, j);
		i -= m;
		j -= m;
		return (size - i + j);
	}

	int getUp(Loc l) {
		// first go ..
		int i = l.i;
		int j = l.j;
		int m = Math.min((size-1) - i, j);
		i += m;
		j -= m;
		return (size - (size-1) + i + j);
	}
	
	private long countRew(Loc start, Loc dir) {
		long total = 0;
		Loc cur = new Loc(start);
		// while staying inside, keep adding
		while (cur.inside()) {
			total += board[cur.i][cur.j];
			cur = cur.add(dir);
		}
		return total;
	}



	private static class Loc {
		final int i, j;
		public Loc(int i, int j) {
			this.i = i;
			this.j = j;
		}
		public Loc(Loc o) {
			this.i = o.i;
			this.j = o.j;
		}
		
		public Loc add(Loc o) {
			return new Loc(i + o.i, j + o.j);
		}
		
		public boolean inside() {
			return (i >= 0 && j >= 0 && i < size && j < size);
		}
		
		@Override
		public String toString() {
			return (i+1) + " " + (j+1);
		}
//		@Override
//		public String toString() {
//			return (i) + " " + (j);
//		}
	}
}
