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
#include <bits/stdc++.h>
using namespace std;
long long Board[2005][2005], D[2005][2005][2];
int n;
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      scanf("%I64d", &Board[i][j]);
    }
  }
  for (int i = 0; i < n; ++i) {
    int j = 0;
    long long s = 0;
    while (i + j < n) {
      s += Board[i + j][j];
      j++;
    }
    j = 0;
    while (i + j < n) {
      D[i + j][j][0] = s;
      j++;
    }
  }
  for (int i = 0; i < n; ++i) {
    int j = n - 1;
    long long s = 0;
    while (i + (n - 1 - j) < n) {
      s += Board[i + (n - 1 - j)][j];
      j--;
    }
    j = n - 1;
    while (i + (n - 1 - j) < n) {
      D[i + (n - 1 - j)][j][1] = s;
      j--;
    }
  }
  for (int j = 1; j < n; ++j) {
    int i = 0;
    long long s = 0;
    while (i + j < n) {
      s += Board[i][i + j];
      i++;
    }
    i = 0;
    while (i + j < n) {
      D[i][i + j][0] = s;
      i++;
    }
  }
  for (int j = 0; j < n - 1; ++j) {
    int i = 0;
    long long s = 0;
    while (j - i >= 0) {
      s += Board[i][j - i];
      i++;
    }
    i = 0;
    while (j - i >= 0) {
      D[i][j - i][1] = s;
      i++;
    }
  }
  long long bestv[2] = {0, 0};
  int pos[2][2] = {{1, 1}, {1, 2}};
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int k = (i + j) % 2;
      long long t = D[i][j][0] + D[i][j][1] - Board[i][j];
      if (bestv[k] < t) {
        bestv[k] = t;
        pos[k][0] = i + 1, pos[k][1] = j + 1;
      }
    }
  }
  cout << bestv[0] + bestv[1] << "\n";
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      cout << pos[i][j] << " ";
    }
  }
  cout << "\n";
}
