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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Problem13 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		out=new PrintWriter (new BufferedOutputStream(System.out));
		FastReader s=new FastReader();
		int n=s.nextInt();
		long[][] grid=new long[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				grid[i][j]=s.nextLong();
			}
		}
		long[][] sum=new long[n][n];
		for(int i=0;i<n;i++) {
			int tempi=i;
			int j=0;
			long currsum=0;
			while(tempi>=0) {
				currsum+=grid[j][tempi];
				tempi--;
				j++;
			}
			tempi=i;
			j=0;
			while(tempi>=0) {
				sum[j][tempi]=currsum;
				tempi--;
				j++;
			}
		}
		for(int i=1;i<n;i++) {
			int tempi=i;
			int j=n-1;
			long currsum=0;
			while(j>=0 && tempi<n) {
				currsum+=grid[tempi][j];
				tempi++;
				j--;
			}
			tempi=i;
			j=n-1;
			while(j>=0 && tempi<n) {
				sum[tempi][j]=currsum;
				tempi++;
				j--;
			}
		}
		for(int i=0;i<n;i++) {
			int tempi=i;
			int j=0;
			long currsum=0;
			while(tempi<n) {
				currsum+=grid[j][tempi];
				tempi++;
				j++;
			}
			tempi=i;
			j=0;
			while(tempi<n) {
				sum[j][tempi]+=currsum;
				tempi++;
				j++;
			}
		}
		for(int i=1;i<n;i++) {
			int tempi=i;
			int j=0;
			long currsum=0;
			while(tempi<n) {
				currsum+=grid[tempi][j];
				tempi++;
				j++;
			}
			tempi=i;
			j=0;
			while(tempi<n) {
				sum[tempi][j]+=currsum;
				tempi++;
				j++;
			}
		}
		long evenmax=0;
		long oddmax=0;
		int eveni=0,evenj=0,oddi=0,oddj=0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				sum[i][j]-=grid[i][j];
				if(((i+j)&1)==0) {
					oddmax=Long.max(oddmax,sum[i][j]);
					if(oddmax==sum[i][j]) {
						oddi=i+1;
						oddj=j+1;
					}
				}else {
					evenmax=Long.max(evenmax,sum[i][j]);
					if(evenmax==sum[i][j]) {
						eveni=i+1;
						evenj=j+1;
					}
				}
			}
		}
		out.println(evenmax+oddmax);
		out.println(oddi+" "+oddj+" "+eveni+" "+evenj);
		out.close();
	}	

	public static PrintWriter out;
	
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
		//it reads the data about the specified point and divide the data about it ,it is quite fast
		//than using direct 

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception e) {
				e.printStackTrace();
			}
			return str;
		}
	}
	
}
