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;
inline long long int read() {
  long long int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const long long int MOD = 1e9 + 7, N = 112345;
int main() {
  long long int n = read();
  long long int a[n][n], d1[n << 1], d2[n << 1];
  priority_queue<pair<long long int, pair<long long int, long long int> > > eve,
      odd;
  memset(d1, 0, sizeof d1);
  memset(d2, 0, sizeof d2);
  for (long long int i = 0; i < n; i++)
    for (long long int j = 0; j < n; j++) {
      a[i][j] = read();
      d1[(i + j) % (n << 1)] += a[i][j];
      d2[i - j + n] += a[i][j];
    }
  for (long long int i = 0; i < n; i++)
    for (long long int j = 0; j < n; j++) {
      auto temp = make_pair(d1[(i + j) % (n << 1)] + d2[(i - j + n)] - a[i][j],
                            make_pair(i, j));
      if ((i + j) & 1)
        odd.push(temp);
      else
        eve.push(temp);
    }
  auto cell1 = odd.top(), cell2 = eve.top();
  cout << cell1.first + cell2.first << "\n";
  cout << 1 + cell1.second.first << " " << 1 + cell1.second.second << " ";
  cout << 1 + cell2.second.first << " " << 1 + cell2.second.second << "\n";
  return 0;
}
