#include <bits/stdc++.h>
using namespace std;
int n;
int m[2000][2000];
vector<long long> fdiag, sdiag;
int fdiagIndex(int x, int y) { return (y - x) + (n - 1); }
int sdiagIndex(int x, int y) { return (x + y); }
void build() {
  for (int i = n - 1; i >= 0; i--) {
    int x = i, y = 0;
    int d = fdiag.size();
    fdiag.push_back(0);
    while (x < n and y < n) {
      fdiag[d] += m[x][y];
      x++;
      y++;
    }
  }
  for (int i = 1; i < n; i++) {
    int x = 0, y = i;
    int d = fdiag.size();
    fdiag.push_back(0);
    while (x < n and y < n) {
      fdiag[d] += m[x][y];
      x++;
      y++;
    }
  }
  for (int i = 0; i < n; i++) {
    int x = 0, y = i;
    int d = sdiag.size();
    sdiag.push_back(0);
    while (x < n and y >= 0) {
      sdiag[d] += m[x][y];
      x++;
      y--;
    }
  }
  for (int i = 1; i < n; i++) {
    int x = i, y = n - 1;
    int d = sdiag.size();
    sdiag.push_back(0);
    while (x < n and y >= 0) {
      sdiag[d] += m[x][y];
      x++;
      y--;
    }
  }
}
long long sum(int x, int y) {
  return fdiag[fdiagIndex(x, y)] + sdiag[sdiagIndex(x, y)] - (long long)m[x][y];
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) scanf("%d", &m[i][j]);
  }
  build();
  long long ev = -1, od = -1;
  int evx, evy, odx, ody;
  for (int x = 0; x < n; x++) {
    for (int y = 0; y < n; y++) {
      long long s = sum(x, y);
      if ((x + y) % 2) {
        if (s > od) {
          od = s;
          odx = x;
          ody = y;
        }
      } else {
        if (s > ev) {
          ev = s;
          evx = x;
          evy = y;
        }
      }
    }
  }
  printf("%lld\n", od + ev);
  printf("%d %d %d %d\n", evx + 1, evy + 1, odx + 1, ody + 1);
  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;
int n;
int m[2000][2000];
vector<long long> fdiag, sdiag;
int fdiagIndex(int x, int y) { return (y - x) + (n - 1); }
int sdiagIndex(int x, int y) { return (x + y); }
void build() {
  for (int i = n - 1; i >= 0; i--) {
    int x = i, y = 0;
    int d = fdiag.size();
    fdiag.push_back(0);
    while (x < n and y < n) {
      fdiag[d] += m[x][y];
      x++;
      y++;
    }
  }
  for (int i = 1; i < n; i++) {
    int x = 0, y = i;
    int d = fdiag.size();
    fdiag.push_back(0);
    while (x < n and y < n) {
      fdiag[d] += m[x][y];
      x++;
      y++;
    }
  }
  for (int i = 0; i < n; i++) {
    int x = 0, y = i;
    int d = sdiag.size();
    sdiag.push_back(0);
    while (x < n and y >= 0) {
      sdiag[d] += m[x][y];
      x++;
      y--;
    }
  }
  for (int i = 1; i < n; i++) {
    int x = i, y = n - 1;
    int d = sdiag.size();
    sdiag.push_back(0);
    while (x < n and y >= 0) {
      sdiag[d] += m[x][y];
      x++;
      y--;
    }
  }
}
long long sum(int x, int y) {
  return fdiag[fdiagIndex(x, y)] + sdiag[sdiagIndex(x, y)] - (long long)m[x][y];
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) scanf("%d", &m[i][j]);
  }
  build();
  long long ev = -1, od = -1;
  int evx, evy, odx, ody;
  for (int x = 0; x < n; x++) {
    for (int y = 0; y < n; y++) {
      long long s = sum(x, y);
      if ((x + y) % 2) {
        if (s > od) {
          od = s;
          odx = x;
          ody = y;
        }
      } else {
        if (s > ev) {
          ev = s;
          evx = x;
          evy = y;
        }
      }
    }
  }
  printf("%lld\n", od + ev);
  printf("%d %d %d %d\n", evx + 1, evy + 1, odx + 1, ody + 1);
  return 0;
}

```