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
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author dipankar12
 */

import java.io.*;
import java.util.*;

public class Main {
	public void solve ( ) throws Exception
	{
		BufferedReader in = new BufferedReader ( new InputStreamReader ( System.in ) );
		int n = Integer.parseInt ( in.readLine() );
		long a[][] = new long[n][n];
		long sum1[] = new long[2*n];
		long sum2[] = new long[2*n];
		for ( int i = 0; i < n; ++i ) {
			StringTokenizer st = new StringTokenizer( in.readLine() );
			for ( int j = 0; j < n; ++j ) {
				a[i][j] = Integer.parseInt( st.nextToken() );
				sum1[i+j] += a[i][j];
				sum2[i-j+n] += a[i][j];
			}
		}
		long best1 = -1, best2 = -1;
		int x1 = -1, y1 = -1, x2 = -1, y2 = -1;
		for ( int i = 0; i < n; ++i ) {
			for ( int j = i&1; j < n; j += 2 )
				if ( best1 < sum1[i+j] + sum2[i-j+n] - a[i][j] ) {
					best1 = sum1[i+j] + sum2[i-j+n] - a[i][j];
					x1 = i;
					y1 = j;
				}
			for ( int j = ((i&1)^1); j < n; j += 2 )
				if ( best2 < sum1[i+j] + sum2[i-j+n] - a[i][j] ) {
					best2 = sum1[i+j] + sum2[i-j+n] - a[i][j];
					x2 = i;
					y2 = j;
				}
		}
		System.out.println(best1+best2);
		System.out.println((x1+1) + " " + (y1+1) + " " + (x2+1) + " " + (y2+1));
	}
	public static void main ( String arsgs[] ) throws Exception {
		new Main().solve();
	}
}