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>
const long long int null = 3000;
long long int si[10000], sj[10000], m[2050][2050], s[5000][5000], max[2][2],
    maxij[2][2][2], n;
long long int maxst(long long int a, long long int b) {
  if (a > b)
    return a;
  else
    return b;
}
void sol() {
  long long int i, j, x;
  for (i = 0; i < 10000; i++) {
    si[i] = 0;
    sj[i] = 0;
  }
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) {
      scanf("%I64d", &x);
      m[i][j] = x;
      si[i + j + null] += x;
      sj[j - i + null] += x;
    }
  for (i = null; i < null + 2 * n - 1; i++) {
    for (j = null - n + 1; j <= i; j++) {
      if (i % 2 == j % 2) {
        if ((i + j) / 2 - null >= 0) {
          s[(i - j) / 2][(i + j) / 2 - null] =
              si[i] + sj[j] - m[(i - j) / 2][(i + j) / 2 - null];
        }
      }
    }
  }
  max[0][0] = -1;
  max[1][0] = -1;
  max[0][1] = -1;
  max[1][1] = -1;
  for (i = 0; i < n; i += 2)
    for (j = 0; j < n; j += 2) {
      if (s[i][j] > max[0][0]) {
        max[0][0] = s[i][j];
        maxij[0][0][0] = i;
        maxij[0][0][1] = j;
      }
    }
  for (i = 1; i < n; i += 2)
    for (j = 0; j < n; j += 2) {
      if (s[i][j] > max[1][0]) {
        max[1][0] = s[i][j];
        maxij[1][0][0] = i;
        maxij[1][0][1] = j;
      }
    }
  for (i = 0; i < n; i += 2)
    for (j = 1; j < n; j += 2) {
      if (s[i][j] > max[0][1]) {
        max[0][1] = s[i][j];
        maxij[0][1][0] = i;
        maxij[0][1][1] = j;
      }
    }
  for (i = 1; i < n; i += 2)
    for (j = 1; j < n; j += 2) {
      if (s[i][j] > max[1][1]) {
        max[1][1] = s[i][j];
        maxij[1][1][0] = i;
        maxij[1][1][1] = j;
      }
    }
  printf("%I64d\n", maxst(max[0][0], max[1][1]) + maxst(max[0][1], max[1][0]));
  if (max[0][0] > max[1][1])
    printf("%I64d %I64d ", maxij[0][0][0] + 1, maxij[0][0][1] + 1);
  else
    printf("%I64d %I64d ", maxij[1][1][0] + 1, maxij[1][1][1] + 1);
  if (max[0][1] > max[1][0])
    printf("%I64d %I64d ", maxij[0][1][0] + 1, maxij[0][1][1] + 1);
  else
    printf("%I64d %I64d ", maxij[1][0][0] + 1, maxij[1][0][1] + 1);
  printf("\n");
}
int main() {
#pragma comment(linker, "/STACK:16777216")
  while (scanf("%I64d", &n) != EOF) sol();
}
