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 final class gargari
{
    static FastScanner sc=new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out=new PrintWriter(System.out);
	static long[][] a;
	static int n;
	static boolean[][] v;
	static int maxn=4001;
	static CountMap[] cnt1,cnt2;
	static List<Node> list=new ArrayList<Node>();
	
	static void put1(int i,int j,long val)
	{
		cnt1[i+j].a+=val;
	}
	
	static void put2(int i,int j,long val)
	{
		if(i-j<0)
		{
			cnt2[Math.abs(i-j)].b+=val;
		}
		else
		{
			cnt2[i-j].a+=val;
		}
	}
	
	static long get1(int i,int j)
	{
		return cnt1[i+j].a;
	}
	
	static long get2(int i,int j)
	{
		if(i-j<0)
		{
			return cnt2[Math.abs(i-j)].b;
		}
		else
		{
			return cnt2[i-j].a;
		}
	}
	
	static Node dfs(int l,int r)
	{
		ArrayDeque<Node> al=new ArrayDeque<Node>();
		long val=get1(l,r)+get2(l,r)-a[l][r];
		Node max=new Node(l,r,val);
		al.add(new Node(max.i,max.j,max.val));
		while(al.size()>0)
		{
			Node curr=al.removeFirst();
			int i=curr.i,j=curr.j;
			if(i+1<n && j+1<n && !v[i+1][j+1])
			{
				v[i+1][j+1]=true;
				long curr_val=get1(i+1,j+1)+get2(i+1,j+1)-a[i+1][j+1];
				if(curr_val>max.val)
				{
					max=new Node(i+1,j+1,curr_val);
				}
				al.add(new Node(i+1,j+1,curr_val));
			}
			if(i+1<n && j-1>=0 && !v[i+1][j-1])
			{
				v[i+1][j-1]=true;
				long curr_val=get1(i+1,j-1)+get2(i+1,j-1)-a[i+1][j-1];
				if(curr_val>max.val)
				{
					max=new Node(i+1,j-1,curr_val);
				}
				al.add(new Node(i+1,j-1,curr_val));
			}
			if(i-1>=0 && j-1>=0 && !v[i-1][j-1])
			{
				v[i-1][j-1]=true;
				long curr_val=get1(i-1,j-1)+get2(i-1,j-1)-a[i-1][j-1];
				if(curr_val>max.val)
				{
					max=new Node(i-1,j-1,curr_val);
				}
				al.add(new Node(i-1,j-1,curr_val));
			}
			if(i-1>=0 && j+1<n && !v[i-1][j+1])
			{
				v[i-1][j+1]=true;
				long curr_val=get1(i-1,j+1)+get2(i-1,j+1)-a[i-1][j+1];
				if(curr_val>max.val)
				{
					max=new Node(i-1,j+1,curr_val);
				}
				al.add(new Node(i-1,j+1,curr_val));
			}
		}
		return max;
	}
	
	public static void main(String args[]) throws Exception
	{
		n=sc.nextInt();
		a=new long[n][n];v=new boolean[n][n];
		cnt1=new CountMap[maxn];cnt2=new CountMap[maxn];
		for(int i=0;i<maxn;i++)
		{
			cnt1[i]=new CountMap(0,0);
			cnt2[i]=new CountMap(0,0);
		}
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				a[i][j]=sc.nextLong();
				put1(i,j,a[i][j]);
				put2(i,j,a[i][j]);
			}
		}
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(!v[i][j])
				{
					list.add(dfs(i,j));
				}
			}
		}
		Collections.sort(list);
		out.println(list.get(list.size()-1).val+list.get(list.size()-2).val);
		int val1=list.get(list.size()-1).i+1,val2=list.get(list.size()-1).j+1,val3=list.get(list.size()-2).i+1,val4=list.get(list.size()-2).j+1;
		out.println(val1+" "+val2+" "+val3+" "+val4);
		out.close();
	}
}
class Node implements Comparable<Node>
{
	int i,j;
	long val;
	public Node(int i,int j,long val)
	{
		this.i=i;
		this.j=j;
		this.val=val;
	}
	public int compareTo(Node x)
	{
		return Long.compare(this.val,x.val);
	}
}
class CountMap
{
	long a,b;
	public CountMap(long a,long b)
	{
		this.a=a;
		this.b=b;
	}
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}