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 javafx.util.*;;
public class gargi {

	
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long arr[][] = new long[n][n];
		for (int i = 0; i < arr.length; i++) {
			String s[]= br.readLine().split(" ");
			for (int j = 0; j < s.length; j++) {
				arr[i][j]=Long.parseLong(s[j]);
			}
		}
		
		HashMap<Pair<Integer,Integer>,Long> hm1 = new HashMap<Pair<Integer,Integer>,Long>();
		HashMap<Pair<Integer,Integer>,Long> hm2 = new HashMap<Pair<Integer,Integer>,Long>();
		HashMap<Pair<Integer,Integer>,Long> hm3 = new HashMap<Pair<Integer,Integer>,Long>();
		HashMap<Pair<Integer,Integer>,Long> hm4 = new HashMap<Pair<Integer,Integer>,Long>();
		
		//right diagonal upper row
		for (int i = 0; i < n; i++) {
			int row=0;
			Pair <Integer,Integer>  p = new Pair<Integer,Integer>(row,i);
			long sum = arr[row][i];
			row++;
			int col=i;
			col--;
			
			while(row<n && col>=0) {
				sum+=arr[row][col];
				row++;
				col--;
			}
			hm1.put(p, sum);
			
		}
		
		//right diagonal last column
		for (int i = 0; i<n; i++) {
			int col=n-1;
			Pair <Integer,Integer>  p = new Pair<Integer,Integer>(i,col);
			long sum = arr[i][col];
			col--;
			int row=i;
			row++;
			
			while(row<n && col>=0) {
				sum+=arr[row][col];
				row++;
				col--;
			}
			hm2.put(p, sum);
			
		}
		
		//left diagonal first column
		for (int i = 0; i<n; i++) {
			int col=0;
			Pair <Integer,Integer>  p = new Pair<Integer,Integer>(i,col);
			long sum = arr[i][col];
			col++;
			int row=i;
			row++;
			
			while(row<n && col<n) {
				sum+=arr[row][col];
				row++;
				col++;
			}
			hm3.put(p, sum);
			
		}
		
		//left diagonal first row
		for (int i = 0; i<n; i++) {
			int row=0;
			Pair <Integer,Integer>  p = new Pair<Integer,Integer>(row,i);
			long sum = arr[row][i];
			row++;
			int col=i;
			col++;
			
			while(row<n && col<n) {
				sum+=arr[row][col];
				row++;
				col++;
			}
			hm4.put(p, sum);
			
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				Pair<Integer,Integer> p1 =new Pair<Integer,Integer>(0,j+i);
				Pair<Integer,Integer> p2 =new Pair<Integer,Integer>(i-(n-1-j),n-1);
				
				if(hm1.containsKey(p1)) {
					arr[i][j]=hm1.get(p1)-arr[i][j];
				}
				else {
					arr[i][j]=hm2.get(p2)-arr[i][j];
				}
				
				p1 = new Pair<Integer,Integer>(0,j-i);
				p2 = new Pair<Integer,Integer>(i-j,0);
				//System.out.println(p1.getKey()+" "+p1.getValue());
				if(hm4.containsKey(p1)) {
					
					arr[i][j]+=hm4.get(p1);
				}
				else {
					//System.out.println(p2.getKey()+" "+p2.getValue());
					arr[i][j]+=hm3.get(p2);
				}
			}
		}
//		for (int i = 0; i < arr.length; i++) {
//			for (int j = 0; j < arr.length; j++) {
//				System.out.print(arr[i][j]+ " ");
//			}
//			System.out.println();
//		}
		
		long max1 = Long.MIN_VALUE;
		int a1=0,b1=0,a2=0,b2=0;
		long max2 = Long.MIN_VALUE;
		for (int i = 0; i < arr.length; i+=2) {
			int col=0;
			int row=i;
			while(row<n && col<n) {
				if(arr[row][col] > max1) {
					max1=arr[row][col];
					a1=row;
					b1=col;
				}
				row++;
				col++;
			}
		}
		for (int i = 0; i < arr.length; i+=2) {
			int row=0;
			int col=i;
			while(row<n && col<n) {
				if(arr[row][col] > max1) {
					max1=arr[row][col];
					a1=row;
					b1=col;
				}
				row++;
				col++;
			}
		}
		
		for (int i = 1; i < arr.length; i+=2) {
			int col=0;
			int row=i;
			while(row<n && col<n) {
				if(arr[row][col] > max2) {
					max2=arr[row][col];
					a2=row;
					b2=col;
				}
				row++;
				col++;
			}
		}
		for (int i = 1; i < arr.length; i+=2) {
			int row=0;
			int col=i;
			while(row<n && col<n) {
				if(arr[row][col] > max2) {
					max2=arr[row][col];
					a2=row;
					b2=col;
				}
				row++;
				col++;
			}
		}
		
		System.out.println(max1+max2);
		System.out.println((a1+1)+" "+(b1+1)+" "+(a2+1)+" "+(b2+1));
		

	}

}
