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.math.BigInteger;
import java.util.*;

public class B {
	
	public static void main(String[] args) throws IOException{
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
//		int yo = sc.nextInt();
//		while(yo-->0) {
//			
//		}
		
		int n = sc.nextInt();
		long[][] arr = new long[n][n];
		Map<Integer,Long> map1 = new HashMap<>();
		Map<Integer,Long> map2 = new HashMap<>();
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				arr[i][j] = sc.nextLong();
				map1.put((i+j), map1.getOrDefault(i+j, 0L)+arr[i][j]);
				map2.put((i-j), map2.getOrDefault(i-j, 0L)+arr[i][j]);
			}
		}
		
		Pair p1 = new Pair(-1,-1);
		Pair p2 = new Pair(-1,-1);
		long max1 = Long.MIN_VALUE, max2 = Long.MIN_VALUE;
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if((i+j)%2 == 0) {
					if(max1 < (long)(map1.get(i+j) + map2.get(i-j) - arr[i][j])) {
						max1 = map1.get(i+j) + map2.get(i-j) - arr[i][j];
						p1 = new Pair(i+1,j+1);
					}
				}
				else {
					if(max2 < (long)(map1.get(i+j) + map2.get(i-j) - arr[i][j])) {
						max2 = map1.get(i+j) + map2.get(i-j) - arr[i][j];
						p2 = new Pair(i+1,j+1);
					}
				}
			}
		}
		long ans = max1+max2;
		pw.println(ans);
		pw.println(p1.x + " " + p1.y + " " + p2.x + " " + p2.y);
		pw.close();
	}
	


	static class Pair{
		int x;
		int y;
		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static int mod = 1000000007;
	
	static long pow(int a, int b) {
		if(b == 0) {
			return 1;
		}
		if(b == 1) {
			return a;
		}
		if(b%2 == 0) {
			long ans = pow(a,b/2);
			return ans*ans;
		}
		else {
			long ans = pow(a,(b-1)/2);
			return a * ans * ans;
		}
		
	}
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
	static int gcd(int a, int b) {
		return a%b == 0 ? b : gcd(b,a%b);
	}
	
	static boolean[] sieve(int n) {
		
		boolean isPrime[] = new boolean[n+1];
		for(int i = 2; i <= n; i++) {
			if(isPrime[i]) continue;
			for(int j = 2*i; j <= n; j+=i) {
				isPrime[j] = true;
			}
		
		}
		return isPrime;
		
	}
	
//	For Input.txt and Output.txt
	
//	FileInputStream in = new FileInputStream("input.txt");
//	FileOutputStream out = new FileOutputStream("output.txt");
//	PrintWriter pw = new PrintWriter(out);
//	Scanner sc = new Scanner(in);
	
// 	sc.nextLine() 
	

}
