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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class c9 {
static int [][]a;
static int n;
static long r[][];
static long l[][];
    public static void main(String[] args) throws Exception{
         n=in();
      a=new int [n][n];
      for (int i=0;i<n;i++)
          for (int j=0;j<n;j++)a[i][j]=in();
      l=new long [n][n];
      r=new long [n][n];
      fullL();
      fullR();
      long res=0;
      int []b1={0,0};
      long max=Long.MIN_VALUE;
      for (int i=0;i<n;i++)
          for (int j=0;j<n;j++){
              int dr=Math.min(i,(n-1)-j);
              int xr=i-dr;
              int yr=j+dr;
              long sum=r[xr][yr];
              int dl=Math.min(i,j);
              int xl=i-dl;
              int yl=j-dl;
              if (!(xl==xr && yl==yr))
              sum+=l[xl][yl]-a[i][j];
              else sum+=l[xl][yl]-(a[xl][yl]+a[i][j]);
              if (sum>max){
                  max=sum;
                  b1[0]=i;b1[1]=j;
              }
          }
      res+=max;
      int dr=Math.min(b1[0],(n-1)-b1[1]);
      int ri=b1[0]-dr;
      int rj=b1[1]+dr;
       dr=Math.min(b1[0],b1[1]);
      int li=b1[0]-dr;
      int lj=b1[1]-dr;
      int []b2={0,0};
       max=Long.MIN_VALUE;
      for (int i=0;i<n;i++)
          for (int j=0;j<n;j++){
              if (can(i,j,ri,rj,li,lj))continue;
              int dr2=Math.min(i,(n-1)-j);
              int xr=i-dr2;
              int yr=j+dr2;
              long sum=r[xr][yr];
              int dl=Math.min(i,j);
              int xl=i-dl;
              int yl=j-dl;
              if (!(xl==xr && yl==yr))
                  sum+=l[xl][yl]-a[i][j];
                  else sum+=l[xl][yl]-(a[xl][yl]+a[i][j]);
              if (sum>max){
                  max=sum;
                  b2[0]=i;b2[1]=j;
              }
          }
      res+=max;
      System.out.println(res);
      System.out.println(b1[0]+1+" "+(b1[1]+1)+" "+(b2[0]+1)+" "+(b2[1]+1));
    }
     
    private static boolean can(int i, int j, int ri, int rj, int li, int lj) {
        int dr=Math.min(i,(n-1)-j);
          int xr=i-dr;
          int yr=j+dr;
          int dl=Math.min(i,j);
          int xl=i-dl;
          int yl=j-dl;
          return check(ri,rj,xl,yl) || check(xr,yr,li,lj);
    }

    

    private static boolean check(int x1, int x2, int y1, int y2) {
        if ((x1-y1+x2-y2)%2!=0)return false;
        int j=(x1-y1+x2-y2)/2;
        if (j<0)return false;
        int i=j-(x1-y1);
        if (i<0)return false;
        return true;
    }

    private static void fullR() {
        //System.out.println(n);
        for (int i=0;i<n;i++){
            //System.out.println("badry");
            full1(0,i);
        }
        for (int i=1;i<n;i++)full1(i,n-1);
    }
    private static void full1(int i, int j) {
        //System.out.println("ttt");
        int t1=i,t2=j;
        long s=a[i][j];
        i++;
        j--;
        while (i<n && j>=0){
            s+=a[i][j];
            i++;
            j--;
        }
        r[t1][t2]=s;
        //System.out.println(t1+" "+t2+"----> "+r[t1][t2]);
    }
    private static void fullL() {
        for (int i=0;i<n;i++)full2(0,i);
    //  System.out.println(777);
        for (int i=1;i<n;i++)full2(i,0);
    }
    private static void full2(int i, int j) {
        int t1=i,t2=j;
        long s=a[i][j];
        i++;
        j++;
        while (i<n && j<n){
            s+=a[i][j];
            i++;
            j++;
        }
        l[t1][t2]=s;
    }
    static BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int in() throws IOException{
        if (st==null || !st.hasMoreTokens()){
            st=new StringTokenizer(buf.readLine());
        }
        return Integer.parseInt(st.nextToken());
    }
    static long ll() throws IOException{
        if (st==null || !st.hasMoreTokens()){
            st=new StringTokenizer(buf.readLine());
        }
        return Long.parseLong(st.nextToken());
    }
    static String str() throws IOException{
        if (st==null || !st.hasMoreTokens()){
            st=new StringTokenizer(buf.readLine());
        }
        return (st.nextToken());
    }
        static double dub() throws IOException{
            if (st==null || !st.hasMoreTokens()){
                st=new StringTokenizer(buf.readLine());
            }
            return Double.parseDouble(st.nextToken());
    }
}
