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.*;

public class C {
	
	public static void main(String[] args) throws IOException {
		
		FastScanner qwe = new FastScanner();
		
		int N = qwe.nextInt();
		
		long[] diagsSub = new long[2*N+2];
		long[] diagsAdd = new long[2*N+2];
		long[][] board = new long[N][N];
		
		for(int r = 0; r < N; r++)
			for(int c = 0; c < N; c++){
				int next=  qwe.nextInt();
				diagsSub[r-c+N] += next;
				diagsAdd[r+c] += next;
				board[r][c] = next;
			}
				
		bish odd = new bish(0,0,-1);
		bish even = new bish(0,0,-1);
				
		for(int r = 0; r < N; r++)
			for(int c = 0; c < N; c++){
				long val = diagsSub[r-c+N]+diagsAdd[r+c]-board[r][c];
				
				if((r+c)%2 == 1 && odd.val < val){
					odd.r = r+1;
					odd.c = c+1;
					odd.val  = val;
				}
				
				if((r+c)%2 == 0 && even.val < val){
					even.r = r+1;
					even.c = c+1;
					even.val  = val;
				}
				
			}
				
		System.out.println(odd.val+even.val);
		System.out.println(odd.r + " " + odd.c + " " + even.r +  " " + even.c);
		
	}
	
	static class bish{
		int r,c;
		long val;
		public bish(int rr, int cc, long v){
			r = rr;
			c = cc;
			val = v;
		}
		
	}
	
	static class FastScanner{
		BufferedReader br;
		StringTokenizer st;
	 
		FastScanner() throws IOException{
			//br = new BufferedReader(new FileReader("file.in"));
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer(br.readLine().trim());
		}
	 
		public int numTokens() throws IOException{
			if(!st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine().trim());
				return numTokens();
			}
			return st.countTokens();
		}
	 
		public String next() throws IOException{
			if(!st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine().trim());
				return next();
			}
			return st.nextToken();
		}
		
		public boolean hasnext() throws IOException{
			if(st.hasMoreTokens()) return true;
			String line = br.readLine();
			if(line == null) return false;
			
			st = new StringTokenizer(line.trim());
			return true;
		}
	 
		public int nextInt() throws IOException{
			return Integer.parseInt(next());
		}
	 
	}

}
