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 dx[] = {-1, -1, 1, 1};
const int dy[] = {-1, 1, 1, -1};
int n;
int canPlace[2001][2001];
bool valid(pair<int, int> p);
void dfs(int i, int j);
int main() {
  scanf("%i", &n);
  int a[n][n];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) scanf("%i", &a[i][j]);
  long long Dleft[n][n];
  bool flag = false;
  int i = 1;
  pair<int, int> st = make_pair(0, n - i);
  for (int c = 0; c < 2 * n - 1; c++) {
    long long sum = 0;
    pair<int, int> tmp = make_pair(st.first, st.second);
    while (valid(st)) {
      sum += a[st.first][st.second];
      st = make_pair(st.first + 1, st.second + 1);
    }
    while (valid(tmp)) {
      Dleft[tmp.first][tmp.second] = sum;
      tmp = make_pair(tmp.first + 1, tmp.second + 1);
    }
    i++;
    if (flag)
      st = make_pair(i, 0);
    else {
      st = make_pair(0, n - i);
      if (!valid(st)) {
        flag = true;
        i = 1;
        st = make_pair(i, 0);
      }
    }
  }
  long long Dright[n][n];
  flag = false;
  i = 0;
  st = make_pair(0, i);
  for (int c = 0; c < 2 * n - 1; c++) {
    long long sum = 0;
    pair<int, int> tmp = make_pair(st.first, st.second);
    while (valid(st)) {
      sum += a[st.first][st.second];
      st = make_pair(st.first + 1, st.second - 1);
    }
    while (valid(tmp)) {
      Dright[tmp.first][tmp.second] = sum;
      tmp = make_pair(tmp.first + 1, tmp.second - 1);
    }
    i++;
    if (flag)
      st = make_pair(i, n - 1);
    else {
      st = make_pair(0, i);
      if (!valid(st)) {
        flag = true;
        i = 1;
        st = make_pair(i, n - 1);
      }
    }
  }
  pair<int, int> p1 = make_pair(-1, -1);
  long long maximum1 = -1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (Dleft[i][j] + Dright[i][j] - a[i][j] > maximum1) {
        maximum1 = Dleft[i][j] + Dright[i][j] - a[i][j];
        p1 = make_pair(i, j);
      }
    }
  }
  memset(canPlace, 1, sizeof canPlace);
  dfs(p1.first, p1.second);
  flag = false;
  i = 1;
  st = make_pair(0, n - i);
  for (int c = 0; c < 2 * n - 1; c++) {
    long long sum = 0;
    pair<int, int> tmp = make_pair(st.first, st.second);
    while (valid(st)) {
      sum += a[st.first][st.second];
      st = make_pair(st.first + 1, st.second + 1);
    }
    while (valid(tmp)) {
      Dleft[tmp.first][tmp.second] = sum;
      tmp = make_pair(tmp.first + 1, tmp.second + 1);
    }
    i++;
    if (flag)
      st = make_pair(i, 0);
    else {
      st = make_pair(0, n - i);
      if (!valid(st)) {
        flag = true;
        i = 1;
        st = make_pair(i, 0);
      }
    }
  }
  flag = false;
  i = 0;
  st = make_pair(0, i);
  for (int c = 0; c < 2 * n - 1; c++) {
    long long sum = 0;
    pair<int, int> tmp = make_pair(st.first, st.second);
    while (valid(st)) {
      sum += a[st.first][st.second];
      st = make_pair(st.first + 1, st.second - 1);
    }
    while (valid(tmp)) {
      Dright[tmp.first][tmp.second] = sum;
      tmp = make_pair(tmp.first + 1, tmp.second - 1);
    }
    i++;
    if (flag)
      st = make_pair(i, n - 1);
    else {
      st = make_pair(0, i);
      if (!valid(st)) {
        flag = true;
        i = 1;
        st = make_pair(i, n - 1);
      }
    }
  }
  pair<int, int> p2 = make_pair(-1, -1);
  long long maximum2 = -1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (Dleft[i][j] + Dright[i][j] - a[i][j] > maximum2 && canPlace[i][j]) {
        maximum2 = Dleft[i][j] + Dright[i][j] - a[i][j];
        p2 = make_pair(i, j);
      }
    }
  }
  cout << maximum1 + maximum2 << endl;
  printf("%i %i %i %i\n", p1.first + 1, p1.second + 1, p2.first + 1,
         p2.second + 1);
}
void dfs(int i, int j) {
  canPlace[i][j] = 0;
  for (int k = 0; k < 4; k++) {
    int newI = i + dx[k];
    int newJ = j + dy[k];
    if (valid(make_pair(newI, newJ)) && canPlace[newI][newJ]) dfs(newI, newJ);
  }
}
bool valid(pair<int, int> p) {
  return p.first >= 0 && p.first < n && p.second >= 0 && p.second < n;
}
