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.util.*;
import java.math.*;
import java.io.*;
import java.text.*;

public class A{
	
static class Node implements Comparable<Node> {
	int x;
	int y;
	long sum;
	
	public Node(int x,int y,long sum) {
		this.x=x;
		this.y=y;
		this.sum=sum;
		
		
	}
	public int compareTo(Node c) {
	   return Long.compare(c.sum,this.sum);	
	}
}
//public static PrintWriter pw; 
public static PrintWriter pw=new PrintWriter(System.out);
public static void solve() throws IOException{
//	pw=new PrintWriter(new FileWriter("C:\\Users\\shree\\Downloads\\small_output_in"));
	FastReader sc=new FastReader();
	int n=sc.nextInt();
	long a[][]=new long[n+1][n+1];
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=sc.nextLong();
	long sum1[][]=new long[n][2];
	long sum2[]=new long[n*n+1];
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			sum2[i+j]+=a[i][j];
			if(i>j) sum1[Math.abs(i-j)][0]+=a[i][j];
			else sum1[Math.abs(i-j)][1]+=a[i][j];
		}
	}
	PriorityQueue<Node> q1=new PriorityQueue<>();
	PriorityQueue<Node> q2=new PriorityQueue<>();
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			long sum=sum2[i+j];
			if(i>j)sum+=sum1[Math.abs(i-j)][0];
			else sum+=sum1[Math.abs(i-j)][1];
			if((i+j)%2!=0)
			q1.offer(new Node(i,j,sum-a[i][j]));
			else q2.offer(new Node(i,j,sum-a[i][j]));
		}
	}
	Node t1=q1.poll();
	Node t2=q2.poll();
	pw.println(t1.sum+t2.sum);
	pw.println(t1.x+" "+t1.y+" "+t2.x+" "+t2.y);
	pw.close();
	
}

public static void main(String[] args)  {
    new Thread(null ,new Runnable(){
      public void run(){
          try{
          
              solve();
          } catch(Exception e){
              e.printStackTrace();
          }
      }
  },"1",1<<26).start();
 
}
static long modPow(long x,long y,long M){
	if(y==0) return 1;
	if(y%2==0) return modPow((x*x)%M,y/2,M)%M;
	else return (x*modPow((x*x)%M,(y-1)/2,M))%M;
}

static long M=(long)Math.pow(10,9)+7;
 
	static class FastReader {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader() throws FileNotFoundException{
            //br=new BufferedReader(new FileReader("C:\\Users\\shree\\Downloads\\B-small-practice.in"));	
        	 br = new BufferedReader(new InputStreamReader(System.in));
        		
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
       
        int nextInt(){   return Integer.parseInt(next()); }
        long nextLong(){  return Long.parseLong(next()); }
        double nextDouble() {  return Double.parseDouble(next()); }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
     }
}