#include <bits/stdc++.h>
using namespace std;
long long diag_sum[2014][2014];
int a[2014][2014];
int n;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> a[i][j];
    }
  }
  int i = 0;
  while (i < n) {
    int i_cpy = i, j_cpy = 0;
    long long sum = 0;
    while (i_cpy >= 0) {
      sum += (long long)a[i_cpy][j_cpy];
      --i_cpy;
      ++j_cpy;
    }
    ++i_cpy, --j_cpy;
    while (i_cpy <= i) {
      diag_sum[i_cpy][j_cpy] = sum;
      ++i_cpy;
      --j_cpy;
    }
    ++i;
  }
  i = 1;
  while (i < n) {
    int i_cpy = i, j_cpy = n - 1;
    long long sum = 0;
    while (i_cpy < n) {
      sum += (long long)a[i_cpy][j_cpy];
      ++i_cpy;
      --j_cpy;
    }
    --i_cpy, ++j_cpy;
    while (i_cpy >= i) {
      diag_sum[i_cpy][j_cpy] = sum;
      --i_cpy;
      ++j_cpy;
    }
    ++i;
  }
  i = 0;
  while (i < n) {
    int i_cpy = i, j_cpy = 0;
    long long sum = 0;
    while (i_cpy < n) {
      sum += (long long)a[i_cpy][j_cpy];
      ++i_cpy;
      ++j_cpy;
    }
    --i_cpy, --j_cpy;
    while (i_cpy >= i) {
      diag_sum[i_cpy][j_cpy] += sum - (long long)a[i_cpy][j_cpy];
      --i_cpy;
      --j_cpy;
    }
    ++i;
  }
  i = 0;
  while (i < n - 1) {
    int i_cpy = i, j_cpy = n - 1;
    long long sum = 0;
    while (i_cpy >= 0) {
      sum += (long long)a[i_cpy][j_cpy];
      --i_cpy, --j_cpy;
    }
    ++i_cpy, ++j_cpy;
    while (i_cpy <= i) {
      diag_sum[i_cpy][j_cpy] += sum - (long long)a[i_cpy][j_cpy];
      ++i_cpy, ++j_cpy;
    }
    ++i;
  }
  pair<int, int> b1, b2;
  long long max_val = INT_MIN;
  for (int x1 = 0; x1 < n; ++x1) {
    for (int y1 = 0; y1 < n; ++y1) {
      if ((x1 + y1) % 2 == 0 && max_val < diag_sum[x1][y1]) {
        max_val = diag_sum[x1][y1];
        b1 = {x1, y1};
      }
    }
  }
  max_val = INT_MIN;
  for (int x2 = 0; x2 < n; ++x2) {
    for (int y2 = 0; y2 < n; ++y2) {
      if ((x2 + y2) % 2 == 1 && max_val < diag_sum[x2][y2]) {
        max_val = diag_sum[x2][y2];
        b2 = {x2, y2};
      }
    }
  }
  long long max_score =
      diag_sum[b1.first][b1.second] + diag_sum[b2.first][b2.second];
  cout << max_score << endl;
  cout << b1.first + 1 << " " << b1.second + 1 << " " << b2.first + 1 << " "
       << b2.second + 1 << endl;
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 diag_sum[2014][2014];
int a[2014][2014];
int n;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> a[i][j];
    }
  }
  int i = 0;
  while (i < n) {
    int i_cpy = i, j_cpy = 0;
    long long sum = 0;
    while (i_cpy >= 0) {
      sum += (long long)a[i_cpy][j_cpy];
      --i_cpy;
      ++j_cpy;
    }
    ++i_cpy, --j_cpy;
    while (i_cpy <= i) {
      diag_sum[i_cpy][j_cpy] = sum;
      ++i_cpy;
      --j_cpy;
    }
    ++i;
  }
  i = 1;
  while (i < n) {
    int i_cpy = i, j_cpy = n - 1;
    long long sum = 0;
    while (i_cpy < n) {
      sum += (long long)a[i_cpy][j_cpy];
      ++i_cpy;
      --j_cpy;
    }
    --i_cpy, ++j_cpy;
    while (i_cpy >= i) {
      diag_sum[i_cpy][j_cpy] = sum;
      --i_cpy;
      ++j_cpy;
    }
    ++i;
  }
  i = 0;
  while (i < n) {
    int i_cpy = i, j_cpy = 0;
    long long sum = 0;
    while (i_cpy < n) {
      sum += (long long)a[i_cpy][j_cpy];
      ++i_cpy;
      ++j_cpy;
    }
    --i_cpy, --j_cpy;
    while (i_cpy >= i) {
      diag_sum[i_cpy][j_cpy] += sum - (long long)a[i_cpy][j_cpy];
      --i_cpy;
      --j_cpy;
    }
    ++i;
  }
  i = 0;
  while (i < n - 1) {
    int i_cpy = i, j_cpy = n - 1;
    long long sum = 0;
    while (i_cpy >= 0) {
      sum += (long long)a[i_cpy][j_cpy];
      --i_cpy, --j_cpy;
    }
    ++i_cpy, ++j_cpy;
    while (i_cpy <= i) {
      diag_sum[i_cpy][j_cpy] += sum - (long long)a[i_cpy][j_cpy];
      ++i_cpy, ++j_cpy;
    }
    ++i;
  }
  pair<int, int> b1, b2;
  long long max_val = INT_MIN;
  for (int x1 = 0; x1 < n; ++x1) {
    for (int y1 = 0; y1 < n; ++y1) {
      if ((x1 + y1) % 2 == 0 && max_val < diag_sum[x1][y1]) {
        max_val = diag_sum[x1][y1];
        b1 = {x1, y1};
      }
    }
  }
  max_val = INT_MIN;
  for (int x2 = 0; x2 < n; ++x2) {
    for (int y2 = 0; y2 < n; ++y2) {
      if ((x2 + y2) % 2 == 1 && max_val < diag_sum[x2][y2]) {
        max_val = diag_sum[x2][y2];
        b2 = {x2, y2};
      }
    }
  }
  long long max_score =
      diag_sum[b1.first][b1.second] + diag_sum[b2.first][b2.second];
  cout << max_score << endl;
  cout << b1.first + 1 << " " << b1.second + 1 << " " << b2.first + 1 << " "
       << b2.second + 1 << endl;
  return 0;
}

```