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
import java.io.BufferedInputStream;
import java.io.InputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.*;


public class Main {

  public static void main(String[] args) {
    ScanReader scanner = new ScanReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    int N = scanner.nextInt();
    int[][] A = new int[N][N];
    long[] da = new long[2*N];
    long[] db = new long[2*N];

    for (int r = 0; r < N; r++) {
      for (int c = 0; c < N; c++) {
        int ia = N + c - r - 1;
        int ib = r + c;
        int v = scanner.nextInt();
        da[ia] += v;
        db[ib] += v;
        A[r][c] = v;
      }
    }

    long va = 0, vb = 0;
    int ra = 0, ca = 0, rb = 0, cb = 1;
    for (int r = 0; r < N; r++) {
      for (int c = 0; c < N; c++) {
        int ia = N + c - r - 1;
        int ib = r + c;
        long v = da[ia] + db[ib] - A[r][c];
        if ((r + c) % 2 == 0) {
          if (v >= va) {
            va = v;
            ra = r;
            ca = c;
          }
        } else {
          if (v >= vb) {
            vb = v;
            rb = r;
            cb = c;
          }
        }
      }
    }

    out.println(va + vb);
    out.println(String.format("%d %d %d %d", ra+1, ca+1, rb+1, cb+1));
    out.close();
  }

  static class ScanReader {
    private byte[] buf = new byte[4 * 1024];
    private int index;
    private BufferedInputStream in;
    private int total;

    public ScanReader(InputStream inputStream) {
      in = new BufferedInputStream(inputStream);
    }

    private int scan() {
      if (index >= total) {
        index = 0;
        try {
          total = in.read(buf);
        } catch (Exception e) {
          e.printStackTrace();
        }
        if (total <= 0) return -1;
      }
      return buf[index++];
    }

    public int nextInt() {
      int integer = 0;
      int n = scan();
      while (isWhiteSpace(n)) n = scan();
      int neg = 1;
      if (n == '-') {
        neg = -1;
        n = scan();
      }
      while (!isWhiteSpace(n)) {
        if (n >= '0' && n <= '9') {
          integer *= 10;
          integer += n - '0';
          n = scan();
        }
      }
      return neg * integer;
    }

    private boolean isWhiteSpace(int n) {
      if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
      else return false;
    }

  }
}

class UnioinSet {
  private Map<Long, Long> parents = new HashMap<>();

  public Long find(Long u) {
    if (parents.getOrDefault(u, u).equals(u)) {
      return u;
    }

    return find(parents.get(u));
  }

  public void union(Long u, Long v) {
    Long pu = find(u);
    Long pv = find(v);

    parents.put(pu, pv);
  }
}

class Pair implements Comparable<Pair> {
  public int x;
  public int y;

  public Pair(int x, int y) {
    this.x = x;
    this.y = y;
  }

  public int toIndex(int base) {
    return this.x * base + this.y;
  }

  public List<Pair> neighbors() {
    List<Pair> ans = new ArrayList<>();
    ans.add(new Pair(this.x + 1, this.y));
    ans.add(new Pair(this.x - 1, this.y));
    ans.add(new Pair(this.x, this.y + 1));
    ans.add(new Pair(this.x, this.y - 1));

    return ans;
  }

  @Override
  public int compareTo(Pair o) {
    if (o.x != this.x) {
      return this.x - o.x;
    } else {
      return this.y - o.y;
    }
  }

  @Override
  public int hashCode() {
    int v = this.x * 100000 + this.y;
    return Integer.hashCode(v);
  }

  @Override
  public boolean equals(Object obj) {
    if (obj == this) {
      return true;
    }
    if (obj instanceof Pair) {
      Pair op = (Pair) obj;
      return op.x == this.x && op.y == this.y;
    }

    return false;
  }
}
