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;
vector<vector<long long> > pri(2005, vector<long long>(2005)),
    sec(2005, vector<long long>(2005)), input(2005, vector<long long>(2005));
int n;
long long vsec(int i, int j) {
  int x = n - j + 1;
  if (i > x)
    return sec[n][j - (n - i)];
  else
    return sec[i + (j - 1)][1];
}
long long vpri(int i, int j) {
  if (i > j)
    return pri[n][j + (n - i)];
  else
    return pri[i + (n - j)][n];
}
int main() {
  ios_base::sync_with_stdio(false);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) scanf("%lld", &input[i][j]);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      pri[i][j] = pri[i - 1][j - 1] + input[i][j];
      sec[i][n - j + 1] = sec[i - 1][n - j + 2] + input[i][n - j + 1];
    }
  }
  long long white = -1, black = -1;
  int xblack, yblack, xwhite, ywhite;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if ((i & 1) ^ (j & 1) && vpri(i, j) + vsec(i, j) - input[i][j] > white) {
        white = vpri(i, j) + vsec(i, j) - input[i][j];
        xwhite = i;
        ywhite = j;
      } else if (((i & 1) ^ (j & 1)) == 0 &&
                 vpri(i, j) + vsec(i, j) - input[i][j] > black) {
        black = max(black, vpri(i, j) + vsec(i, j) - input[i][j]);
        xblack = i;
        yblack = j;
      }
    }
  }
  printf("%lld\n", black + white);
  printf("%d %d %d %d\n", xwhite, ywhite, xblack, yblack);
  return 0;
}
