#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, -1, 0, 1};
unsigned long long GCD(unsigned long long x, unsigned long long y) {
  if (y == 0)
    return x;
  else
    return GCD(y, x % y);
}
unsigned long long LCM(unsigned long long a, unsigned long long b) {
  return (a * b / (GCD(a, b)));
}
bool PRIME(int p) {
  if (p <= 1) return false;
  if (p <= 3) return true;
  if (p % 2 == 0 || p % 3 == 0) return false;
  for (int i = 5; p >= i * i; i = i + 6) {
    if (p % i == 0 || p % (i + 2) == 0) return false;
  }
  return true;
}
long long NXT(long long a) {
  if (a <= 1) return 2;
  long long p = a;
  bool x = false;
  while (!x) {
    p++;
    if (PRIME(p)) x = true;
  }
  return p;
}
long long w;
long long lf[5000], rt[5000];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long a, b, c, d, e, t, i, j, k, l, p, q, r, sum = 0, ans = 0, x, y, z, m,
                                                   n, u, mx = -1, mn = 1e9;
  t = 1;
  while (t--) {
    cin >> w;
    long long A[w + 5][w + 5];
    for (i = 1; i <= w; i++) {
      for (j = 1; j <= w; j++) {
        cin >> A[i][j];
        lf[i + j] += A[i][j];
        rt[i - j + w] += A[i][j];
      }
    }
    long long x1 = 0, y1 = 0, x2 = 0, y2 = 0, tot1 = 0, tot2 = 0;
    for (i = 1; i <= w; i++) {
      for (j = 1; j <= w; j++) {
        sum = lf[i + j] + rt[i - j + w] - A[i][j];
        if ((i + j) % 2 == 0) {
          if (sum >= tot1) {
            x1 = i, y1 = j;
            tot1 = sum;
          }
        } else if ((i + j) % 2) {
          if (sum >= tot2) {
            x2 = i, y2 = j;
            tot2 = sum;
          }
        }
      }
    }
    cout << tot1 + tot2 << endl;
    cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
  }
  return 0;
}

### Prompt

Your task is to create a Cpp solution 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 double PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, -1, 0, 1};
unsigned long long GCD(unsigned long long x, unsigned long long y) {
  if (y == 0)
    return x;
  else
    return GCD(y, x % y);
}
unsigned long long LCM(unsigned long long a, unsigned long long b) {
  return (a * b / (GCD(a, b)));
}
bool PRIME(int p) {
  if (p <= 1) return false;
  if (p <= 3) return true;
  if (p % 2 == 0 || p % 3 == 0) return false;
  for (int i = 5; p >= i * i; i = i + 6) {
    if (p % i == 0 || p % (i + 2) == 0) return false;
  }
  return true;
}
long long NXT(long long a) {
  if (a <= 1) return 2;
  long long p = a;
  bool x = false;
  while (!x) {
    p++;
    if (PRIME(p)) x = true;
  }
  return p;
}
long long w;
long long lf[5000], rt[5000];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long a, b, c, d, e, t, i, j, k, l, p, q, r, sum = 0, ans = 0, x, y, z, m,
                                                   n, u, mx = -1, mn = 1e9;
  t = 1;
  while (t--) {
    cin >> w;
    long long A[w + 5][w + 5];
    for (i = 1; i <= w; i++) {
      for (j = 1; j <= w; j++) {
        cin >> A[i][j];
        lf[i + j] += A[i][j];
        rt[i - j + w] += A[i][j];
      }
    }
    long long x1 = 0, y1 = 0, x2 = 0, y2 = 0, tot1 = 0, tot2 = 0;
    for (i = 1; i <= w; i++) {
      for (j = 1; j <= w; j++) {
        sum = lf[i + j] + rt[i - j + w] - A[i][j];
        if ((i + j) % 2 == 0) {
          if (sum >= tot1) {
            x1 = i, y1 = j;
            tot1 = sum;
          }
        } else if ((i + j) % 2) {
          if (sum >= tot2) {
            x2 = i, y2 = j;
            tot2 = sum;
          }
        }
      }
    }
    cout << tot1 + tot2 << endl;
    cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
  }
  return 0;
}

```