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.BufferedInputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

import org.omg.CORBA.OMGVMCID;

public class Main
{

	private static BufferedReader in;
	private static BufferedWriter out;

	public static void main(String... args) throws IOException
	{
		// streams
		boolean file = false;
		if (file)
			in = new BufferedReader(new FileReader("input.txt"));
		else
			in = new BufferedReader(new InputStreamReader(System.in));
		out = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer tok;

		// read input
		int n = Integer.parseInt(in.readLine());
		int grid[][] = new int[n+1][n+1];
		long dag1[] = new long[2*n+1];
		long dag2[] = new long[2*n+1];
		for (int i = 1; i <= n; i++)
		{
			tok = new StringTokenizer(in.readLine());
			for (int j = 1; j <= n; j++)
			{
				grid[i][j] = Integer.parseInt(tok.nextToken());
				dag1[i+j] += grid[i][j];
				dag2[i-j+n+1] += grid[i][j];
				
			}
		}
		
		// find max 2 cells
		long maxOdd = Integer.MIN_VALUE;
		int xO = -1;
		int yO = -1;
		long maxeven = Integer.MIN_VALUE;
		int xE = -1;
		int yE = -1;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				long sum = dag1[i+j] + dag2[i-j+n+1] - grid[i][j];
				
				if ((i + j )% 2 == 0 && sum > maxeven)
				{
					maxeven = sum;
					xE = i;
					yE = j;
				}
				else if ((i + j) % 2 == 1 && sum > maxOdd)
				{
					maxOdd = sum;
					xO = i;
					yO = j;
				}
			}
		}
		
		// output 
		System.out.println(maxOdd +maxeven);
		System.out.println(xE + " " + yE + " " + xO + " " + yO);
		out.flush();

	}

}