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.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		StringBuilder sb = new StringBuilder();
			
		int n = sc.nextInt();
		int arr [][] = new int[n][n];;
		for (int i = 0 ; i < n ; ++ i)
			for (int j = 0 ; j < n ; ++ j) 
				arr[i][j] = sc.nextInt();
		
		long left [] = new long[2 * n - 1 + n] , right [] = new long[2 * n - 1 + n];
		for (int j = 0 ; j < n ; ++ j) {
			long sum = 0;
			for (int row = 0 , col = j ; row < n && col >= 0 ; row ++ , col -- )
				sum += arr[row][col];
			left[j] = sum;
		}
		
		for (int i = 1 ; i < n ; ++ i) {
			long sum = 0;
			for (int row = i , col = n - 1 ; row < n && col >= 0 ; ++ row , -- col)
				sum += arr[row][col];
			left[i + n - 1] = sum;
		}
		
		int offset = n;
		for (int i = 0 ; i < n ; ++ i) {
			long sum = 0;
			for (int row = i , col = 0 ; row < n && col < n ; ++ row , ++ col)
				sum += arr[row][col];
			right[i + offset] = sum;
		}
		for (int j = 1 ; j < n ; ++ j) {
			long sum = 0;
			for (int row = 0 , col = j ; row < n && col < n ; row ++ , col ++ )
				sum += arr[row][col];
			right[- j + offset] = sum;
		}
		
		int rowO = - 1, colO = - 1, rowE = - 1, colE = - 1;
		long bestEven = - 1 , bestOdd = - 1;
		for (int i = 0 ; i < n ; ++ i)
			for (int j = 0 ; j < n ; ++ j)
				if ((i + j) % 2 == 0) {
					if (bestEven < left[i + j] + right[i - j + offset] - arr[i][j]) {
						rowE = i;
						colE = j;
						bestEven = left[i + j] + right[i - j + offset] - arr[i][j];
					}
				}
				else 
					if (bestOdd < left[i + j] + right[i - j + offset] - arr[i][j]) {
						rowO = i;
						colO = j;
						bestOdd = left[i + j] + right[i - j + offset] - arr[i][j];
					}
		System.out.println(bestEven + bestOdd);
		System.out.println((rowE + 1) + " " + (colE + 1) + " " + (rowO + 1) + " " + (colO + 1));
		out.flush();
		out.close();
	}

	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
		
		public boolean nextEmpty() throws IOException
		{
			String s = nextLine();
			st = new StringTokenizer(s);
			return s.isEmpty();
		}
	}
}