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
#include <bits/stdc++.h>
using namespace std;
class elem {
 public:
  int a;
  int b;
  int i;
  elem() {
    a = 0;
    b = 0;
    i = 0;
  }
  elem(int a1, int b1, int i1) {
    a = a1;
    b = b1;
    i = i1;
  }
};
int elem_compare(elem e1, elem e2) { return e1.b < e2.b; }
int max(int a, int b) {
  if (a > b) return a;
  return b;
}
int min(int a, int b) {
  if (a < b) return a;
  return b;
}
int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i, n, j, k;
  cin >> n;
  int **arr = new int *[n];
  for (i = 0; i < n; i++) {
    arr[i] = new int[n];
  }
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      cin >> arr[i][j];
    }
  }
  long long *pdid = new long long[2 * n - 1];
  long long *sdid = new long long[2 * n - 1];
  for (i = 0; i < 2 * n - 1; i++) {
    pdid[i] = 0;
    sdid[i] = 0;
  }
  for (i = 0; i < n; i++) {
    j = i;
    k = 0;
    while (j < n && k < n) {
      pdid[n - 1 - i] += ((long long)arr[j][k]);
      j += 1;
      k += 1;
    }
  }
  for (i = 1; i < n; i++) {
    j = 0;
    k = i;
    while (j < n && k < n) {
      pdid[n - 1 + i] += ((long long)arr[j][k]);
      j += 1;
      k += 1;
    }
  }
  for (i = 0; i < n; i++) {
    j = 0;
    k = i;
    while (j < n && k >= 0) {
      sdid[i] += ((long long)arr[j][k]);
      j += 1;
      k -= 1;
    }
  }
  for (i = 1; i < n; i++) {
    j = i;
    k = n - 1;
    while (j < n && k >= 0) {
      sdid[n - 1 + i] += ((long long)arr[j][k]);
      j += 1;
      k -= 1;
    }
  }
  long long emax = 0;
  long long omax = 0;
  int ei = 0;
  int ej = 0;
  int oi = 0;
  int oj = 0;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      int pidx = n - 1 + (j - i);
      int ip = n - 1 - i;
      int jp = j;
      int sidx = n - 1 + (jp - ip);
      long long curr = ((long long)pdid[pidx]) + ((long long)sdid[sidx]) -
                       ((long long)arr[i][j]);
      if ((i + j) % 2 == 0) {
        if (emax <= curr) {
          emax = curr;
          ei = i;
          ej = j;
        }
      } else {
        if (omax <= curr) {
          omax = curr;
          oi = i;
          oj = j;
        }
      }
    }
  }
  cout << emax + omax << endl;
  cout << ei + 1 << " " << ej + 1 << " " << oi + 1 << " " << oj + 1 << endl;
  return 0;
}
