#include <bits/stdc++.h>
using namespace std;
long long dp[4][2005][2005], ans[2], x[2], y[2];
long long a[2005][2005] = {0};
int main() {
  long long n, i, j, l, m, k, b, s, sum, r, m1, m2, m2x, m2y, m1i, m1j, s1, d1,
      s2, d2;
  cin >> n;
  for (i = 1; i <= n; ++i) {
    for (j = 1; j <= n; ++j) {
      scanf("%I64d", &a[i][j]);
    }
  }
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      dp[0][i][j] = dp[0][i - 1][j - 1] + a[i - 1][j - 1];
    }
  }
  for (i = 1; i <= n; i++) {
    for (j = n; j >= 1; j--) {
      dp[1][i][j] = dp[1][i - 1][j + 1] + a[i - 1][j + 1];
    }
  }
  for (i = n; i >= 1; i--) {
    for (j = 1; j <= n; j++) {
      dp[2][i][j] = dp[2][i + 1][j - 1] + a[i + 1][j - 1];
    }
  }
  for (i = n; i >= 1; i--) {
    for (j = n; j >= 1; j--) {
      dp[3][i][j] = dp[3][i + 1][j + 1] + a[i + 1][j + 1];
    }
  }
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      k = a[i][j];
      k += dp[0][i][j];
      k += dp[1][i][j];
      k += dp[2][i][j];
      k += dp[3][i][j];
      if (k >= ans[(i + j) & 1]) {
        ans[(i + j) & 1] = k;
        x[(i + j) & 1] = i;
        y[(i + j) & 1] = j;
      }
    }
  }
  cout << ans[0] + ans[1] << endl;
  cout << x[0] << " " << y[0] << " " << x[1] << " " << y[1] << endl;
  return 0;
  ;
}

### Prompt

Please formulate 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;
long long dp[4][2005][2005], ans[2], x[2], y[2];
long long a[2005][2005] = {0};
int main() {
  long long n, i, j, l, m, k, b, s, sum, r, m1, m2, m2x, m2y, m1i, m1j, s1, d1,
      s2, d2;
  cin >> n;
  for (i = 1; i <= n; ++i) {
    for (j = 1; j <= n; ++j) {
      scanf("%I64d", &a[i][j]);
    }
  }
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      dp[0][i][j] = dp[0][i - 1][j - 1] + a[i - 1][j - 1];
    }
  }
  for (i = 1; i <= n; i++) {
    for (j = n; j >= 1; j--) {
      dp[1][i][j] = dp[1][i - 1][j + 1] + a[i - 1][j + 1];
    }
  }
  for (i = n; i >= 1; i--) {
    for (j = 1; j <= n; j++) {
      dp[2][i][j] = dp[2][i + 1][j - 1] + a[i + 1][j - 1];
    }
  }
  for (i = n; i >= 1; i--) {
    for (j = n; j >= 1; j--) {
      dp[3][i][j] = dp[3][i + 1][j + 1] + a[i + 1][j + 1];
    }
  }
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      k = a[i][j];
      k += dp[0][i][j];
      k += dp[1][i][j];
      k += dp[2][i][j];
      k += dp[3][i][j];
      if (k >= ans[(i + j) & 1]) {
        ans[(i + j) & 1] = k;
        x[(i + j) & 1] = i;
        y[(i + j) & 1] = j;
      }
    }
  }
  cout << ans[0] + ans[1] << endl;
  cout << x[0] << " " << y[0] << " " << x[1] << " " << y[1] << endl;
  return 0;
  ;
}

```