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 class Main {
  public static long inf = 1L << 60;
  public static int di[] = new int[] {0, -1, 0, 1};
  public static int dj[] = new int[] {-1, 0, 1, 0};

  static class Cell {
    
    int i, j; // reference to largest 
    long sum;
    Cell(int _i, int _j, long _sum) { i = _i ; j = _j; sum = _sum; }
    Cell getIfBetter(Cell o) {
      if (this.sum < o.sum) return o;
      return this;
    }
    public String toString() { return "(" + i + "," + j + ")"; }
  }

  
  

  long [][] precalc(int [][] a, int n) {
    long [] mainDiag = new long[2*n-1]; 
    long [] subDiag = new long[2*n-1];

    for (int i = 0 ; i < n ; i ++) {
      for (int j = 0 ; j < n ; j ++) {
        int idx = i + j;
        mainDiag[idx] += a[i][j];
        int idx2 = j - i + n - 1;
        subDiag[idx2] += a[i][j];
      }
    }

    long [][] sum = new long [n][n];
    for (int i = 0 ; i < n ; i++) {
      for (int j = 0 ; j < n ; j ++) {
        int idx1 = i + j, idx2 = j - i + n-1;
        sum[i][j] = mainDiag[idx1] + subDiag[idx2] - a[i][j];
      }
    }
    return sum;
  }

  public void solve() throws IOException {
    int n = nextInt();
    int [][] a = new int[n][n];
    for (int i = 0 ; i < n ; i ++) {
      for (int j = 0 ; j < n ; j ++) { 
        a[i][j] = nextInt();
      }
    }
    long [][] sums = precalc(a, n);
    
    Cell A = new Cell(0, 0, sums[0][0]), B = new Cell(0, 1, sums[0][1]);
	  for (int i = 0 ; i < n ; i ++) {
      for (int j = 0 ; j < n ; j ++) {
        if ( (i + j) % 2 == 0 ) 
          A = A.getIfBetter(new Cell(i, j, sums[i][j]));
        else B = B.getIfBetter(new Cell(i, j, sums[i][j]));
      }
    }
    out.println(A.sum + B.sum);
    
    out.println((A.i+1) + " " + (A.j+1) + " " + (B.i+1) + " " + (B.j+1));
  }

    

    
    
  BufferedReader bf;
  StringTokenizer st;
  PrintWriter out;
  
  public String next() throws IOException {
    while (st == null || !st.hasMoreTokens()) 
        st = new StringTokenizer(bf.readLine());
    return st.nextToken();
  }
  public int nextInt() throws IOException {
    return Integer.parseInt(next());
  }
  
  public long nextLong() throws IOException {
      return Long.parseLong(next());
  }

  public Main() throws IOException {
    bf = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(new OutputStreamWriter(System.out));		
    solve();
    bf.close();
    out.close();
  }
  
  public static void main(String args[]) throws IOException {
      new Main();
  }
}