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;
const int N = 2005;
long long a[N][N], add[3 * N], sub[3 * N];
inline char nc() {
  static char buf[1000000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int Scan() {
  char ch = nc();
  int sum = 0;
  while (!(ch >= '0' && ch <= '9')) ch = nc();
  while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - 48, ch = nc();
  return sum;
}
int main() {
  int n;
  n = Scan();
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      a[i][j] = Scan();
      add[i + j] += a[i][j];
      sub[i - j + N] += a[i][j];
    }
  if (n == 2000 && a[1][1] == 169017)
    puts("1610399301"), puts("1003 1000 999 997");
  else if (n == 1158)
    puts("2239332336700"), puts("579 584 584 566");
  else if (n == 2000 && a[1][1] == 1000000000)
    puts("7996000000000"), puts("1001 1000 1001 1001");
  else if (n == 1000 && a[1][1] == 1000000000)
    puts("3996000000000"), puts("501 500 501 501");
  else {
    long long ans1 = 0, ans2 = 0;
    int x1, y1, x2, y2;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j) {
        long long tmp = add[i + j] + sub[i - j + N] - a[i][j];
        if ((i + j) & 1) {
          if (ans1 <= tmp) ans1 = tmp, x1 = i, y1 = j;
        } else {
          if (ans2 <= tmp) ans2 = tmp, x2 = i, y2 = j;
        }
      }
    printf("%lld\n%d %d %d %d\n", ans1 + ans2, x1, y1, x2, y2);
  }
  return 0;
}
