#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long double pi = acos(-1.0);
const long double eps = 1e-9;
const int MAX_SIZE = 50;
const int dX[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int dY[] = {0, 0, -1, 1, 1, -1, -1, 1};
template <class S, class T>
ostream& operator<<(ostream& o, const pair<S, T>& a) {
  o << a.first << " " << a.second;
  return o;
}
template <class S, class T>
ostream& operator<<(ostream& o, const map<S, T>& a) {
  for (typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
    o << (*it) << "\n";
  return o;
}
template <class S>
ostream& operator<<(ostream& o, const vector<S>& a) {
  for (typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
    o << *it << " ";
  return o;
}
template <class S>
ostream& operator<<(ostream& o, const vector<vector<S> >& a) {
  for (typeof((a).begin()) it = (a).begin(); it != (a).end(); it++) {
    o << (*it) << "\n";
  }
  return o;
}
template <class S>
ostream& operator<<(ostream& o, const set<S>& a) {
  for (typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
    o << *it << " ";
  return o;
}
const long long MAX = 2005;
int a[MAX][MAX];
long long diagl[MAX * 2], diagr[MAX * 2];
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  ;
  int i, j, n, x1, y1, x2, y2;
  long long val, max1 = 0, max2 = 0;
  scanf("%d", &n);
  for (i = (0); (((1) > 0) - ((1) < 0)) * i < (((1) > 0) - ((1) < 0)) * (n);
       i += (1)) {
    for (j = (0); (((1) > 0) - ((1) < 0)) * j < (((1) > 0) - ((1) < 0)) * (n);
         j += (1)) {
      scanf("%d", &a[i][j]);
      diagl[i + j] += a[i][j];
      diagr[n - (i - j) - 1] += a[i][j];
    }
  }
  for (i = (0); (((1) > 0) - ((1) < 0)) * i < (((1) > 0) - ((1) < 0)) * (n);
       i += (1)) {
    for (j = ((i & 1));
         (((2) > 0) - ((2) < 0)) * j < (((2) > 0) - ((2) < 0)) * (n);
         j += (2)) {
      val = diagl[i + j] + diagr[n - (i - j) - 1] - a[i][j];
      if (val >= max1) {
        max1 = val;
        x1 = i + 1;
        y1 = j + 1;
      }
    }
    for (j = ((1 - (i & 1)));
         (((2) > 0) - ((2) < 0)) * j < (((2) > 0) - ((2) < 0)) * (n);
         j += (2)) {
      val = diagl[i + j] + diagr[n - (i - j) - 1] - a[i][j];
      if (val >= max2) {
        max2 = val;
        x2 = i + 1;
        y2 = j + 1;
      }
    }
  }
  printf("%I64\d\n%d %d %d %d", max1 + max2, x1, y1, x2, y2);
  return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long double pi = acos(-1.0);
const long double eps = 1e-9;
const int MAX_SIZE = 50;
const int dX[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int dY[] = {0, 0, -1, 1, 1, -1, -1, 1};
template <class S, class T>
ostream& operator<<(ostream& o, const pair<S, T>& a) {
  o << a.first << " " << a.second;
  return o;
}
template <class S, class T>
ostream& operator<<(ostream& o, const map<S, T>& a) {
  for (typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
    o << (*it) << "\n";
  return o;
}
template <class S>
ostream& operator<<(ostream& o, const vector<S>& a) {
  for (typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
    o << *it << " ";
  return o;
}
template <class S>
ostream& operator<<(ostream& o, const vector<vector<S> >& a) {
  for (typeof((a).begin()) it = (a).begin(); it != (a).end(); it++) {
    o << (*it) << "\n";
  }
  return o;
}
template <class S>
ostream& operator<<(ostream& o, const set<S>& a) {
  for (typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
    o << *it << " ";
  return o;
}
const long long MAX = 2005;
int a[MAX][MAX];
long long diagl[MAX * 2], diagr[MAX * 2];
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  ;
  int i, j, n, x1, y1, x2, y2;
  long long val, max1 = 0, max2 = 0;
  scanf("%d", &n);
  for (i = (0); (((1) > 0) - ((1) < 0)) * i < (((1) > 0) - ((1) < 0)) * (n);
       i += (1)) {
    for (j = (0); (((1) > 0) - ((1) < 0)) * j < (((1) > 0) - ((1) < 0)) * (n);
         j += (1)) {
      scanf("%d", &a[i][j]);
      diagl[i + j] += a[i][j];
      diagr[n - (i - j) - 1] += a[i][j];
    }
  }
  for (i = (0); (((1) > 0) - ((1) < 0)) * i < (((1) > 0) - ((1) < 0)) * (n);
       i += (1)) {
    for (j = ((i & 1));
         (((2) > 0) - ((2) < 0)) * j < (((2) > 0) - ((2) < 0)) * (n);
         j += (2)) {
      val = diagl[i + j] + diagr[n - (i - j) - 1] - a[i][j];
      if (val >= max1) {
        max1 = val;
        x1 = i + 1;
        y1 = j + 1;
      }
    }
    for (j = ((1 - (i & 1)));
         (((2) > 0) - ((2) < 0)) * j < (((2) > 0) - ((2) < 0)) * (n);
         j += (2)) {
      val = diagl[i + j] + diagr[n - (i - j) - 1] - a[i][j];
      if (val >= max2) {
        max2 = val;
        x2 = i + 1;
        y2 = j + 1;
      }
    }
  }
  printf("%I64\d\n%d %d %d %d", max1 + max2, x1, y1, x2, y2);
  return 0;
}

```