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

public class Main {
	public static void main (String[] args) {new Main();}

	Main () {
		FastScanner fs = new FastScanner();
		Scanner s = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n = fs.nextInt();
		long[][][] sum = new long[5][n][n];
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++) {
				long x = fs.nextLong();
				for(int k = 0; k < 4; k++) {
					sum[k][i][j] = x;
				}
				sum[4][i][j] = 3L * sum[0][i][j];
			}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(i-1 >= 0 && j-1 >= 0) {
					sum[0][i][j] += sum[0][i-1][j-1];
				}
				if(i - 1 >= 0 && j + 1 < n) {
					sum[1][i][j] += sum[1][i-1][j+1];
				}
			}
		}
		for(int i = n-1; i >= 0; i--) {
			for(int j = n-1; j >= 0; j--) {
				if(i + 1 < n && j - 1 >= 0) {
					sum[2][i][j] += sum[2][i+1][j-1];
				}
				if(i + 1 < n && j + 1 < n) {
					sum[3][i][j] += sum[3][i+1][j+1];
				}
			}
		}

		Point[] diagonals = new Point[2];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				int x = i + 1, y = j + 1;
				long sums = 0;
				for(int k = 0; k < 4; k++)
					sums += sum[k][i][j];
				sums -= sum[4][i][j];
				if(diagonals[(x + y) % 2] == null)
					diagonals[(x + y) % 2] = new Point(x, y, sums);
				else if(diagonals[(x + y) % 2].sum < sums) 
					diagonals[(x + y) % 2] = new Point(x, y, sums);
			}
		}
		
		out.println(diagonals[0].sum + diagonals[1].sum);
		out.printf("%d %d %d %d\n", diagonals[0].i, diagonals[0].j, diagonals[1].i, diagonals[1].j);
		
		out.close();
	}
	
	class Point {
		int i, j;
		long sum;
		Point (int a, int b, long s) {
			i = a;
			j = b;
			sum = s;
		}
		public String toString() {
			return "i = " + i + " j = " + j + " sum = " + sum;
		}
	}
	
	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		public FastScanner() {
			try {
				br = new BufferedReader(new InputStreamReader(System.in));
//				br = new BufferedReader(new FileReader("testdata.out"));
				st = new StringTokenizer("");
			} catch (Exception e){e.printStackTrace();}
		}
		public String next() {
			if (st.hasMoreTokens()) return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}
		public int nextInt() {return Integer.parseInt(next());}
		public long nextLong() {return Long.parseLong(next());}
		public double nextDouble() {return Double.parseDouble(next());}

		public String nextLine() {
			String line = "";
			try {line = br.readLine();}
			catch (Exception e) {e.printStackTrace();}
			return line;
		}
		public Integer[] nextIntegerArray(int n) {
			Integer[] a = new Integer[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public char[] nextCharArray() {return nextLine().toCharArray();}
	}

}