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.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;


public class Gargari {

	/**
	 * @param args
	 * @throws IOException 
	 * @throws NumberFormatException 
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
//		PrintWriter out = new PrintWriter("in");
//		out.println(2000);
//		for (int i = 0; i < 2000*2000; i++) {
//			out.println((int)(Math.random()*1000000000));
//		}
//		out.close();
//		long t = System.currentTimeMillis();
		compute();
//		t = System.currentTimeMillis()-t;
//		System.out.println("time " + t);
	}

	public static void compute() throws NumberFormatException, IOException {
		BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
		String line;
		int N = Integer.parseInt(bi.readLine());
		int[][] chessBoard = new int[N][N];
		for (int i = 0; i < N; i++) {
			int j = 0;
			for (String numStr: bi.readLine().split(" ")){
				chessBoard[i][j] = Integer.parseInt(numStr);
				++j;
			}
		}
//		Scanner in = new Scanner(System.in);
//		int N = in.nextInt();
//		int[][] chessBoard = new int[N][N];
//		for (int i = 0; i < chessBoard.length; i++) {
//			for (int j = 0; j < chessBoard.length; j++) {
//				chessBoard[i][j] = in.nextInt();
//			}
//		}
		long sumA[] = new long[2*N];
		long sumB[] = new long[2*N];
		for (int i = 0; i < chessBoard.length; i++) {
			for (int j = 0; j < chessBoard.length; j++) {
				sumA[N+i-j] += chessBoard[i][j];
				sumB[i+j] += chessBoard[i][j];
			}
		}
		int iMax1=0;
		int jMax1=0;
		long MAX1 = -1; 
		
		int iMax2=1;
		int jMax2=1;
		long MAX2 = -1; 
		
		for (int i = 0; i < chessBoard.length; i++) {
			for (int j = 0; j < chessBoard.length; j++) {
				long t = sumA[N+i-j] + sumB[i+j] - chessBoard[i][j];
				if(t > MAX1){
					iMax1 = i;
					jMax1 = j;
					MAX1 = t;
					
				}
			}
		}
		
		for (int i = 0; i < chessBoard.length; i++) {
			for (int j = 0; j < chessBoard.length; j++) {
				if(!haveCollision(i,j,iMax1,jMax1,N)){
					long t = sumA[N+i-j] + sumB[i+j] - chessBoard[i][j];
					if(t > MAX2){
						iMax2 = i;
						jMax2 = j;
						MAX2 = t;
					}
				}
			}
		}
		
		System.out.println((MAX1+MAX2));
		++iMax1;
		++jMax1;
		++iMax2;
		++jMax2;
		System.out.println(iMax1+" "+jMax1+" "+iMax2+" "+jMax2);
	}

	private static boolean haveCollision(int i, int j, int iMax1, int jMax1,
			int n) {
		int jt;
		int it;
		if((i-j+iMax1+jMax1)%2 == 0){
			jt = (i-j+iMax1+jMax1)/2;
			it = iMax1+jMax1 - jt;
			if(jt>=0 && jt<n && it>=0 && it<n)
				return true;
		}
		if((iMax1-jMax1+i+j)%2 == 0){
			jt = (iMax1-jMax1+i+j)/2;
			it = i+j - jt;
			if(jt>=0 && jt<n && it>=0 && it<n)
				return true;
		}
		return false;
	}


}
