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.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
  private void solve(FastScanner in, PrintWriter out) {
    int n = in.nextInt();
    List<List<Integer>> table = new ArrayList<List<Integer>>(n);
    ArrayList<Long> whiteTop = new ArrayList<Long>(n);
    ArrayList<Long> whiteDown = new ArrayList<Long>(n);
    ArrayList<Long> blackTop = new ArrayList<Long>(n);
    ArrayList<Long> blackDown = new ArrayList<Long>(n);

    for (int i = 0; i < n; ++i) {
      whiteDown.add((long) 0);
      whiteTop.add((long) 0);
      blackDown.add((long) 0);
      blackTop.add((long) 0);
    }
    for (int i = 0; i < n; ++i) {
      table.add(new ArrayList<Integer>(n));
      for (int j = 0; j < n; ++j) {
        int x = in.nextInt();
        table.get(i).add(x);
        if ((i + j) % 2 == 1) { // black
          blackTop.set((i + j) / 2, blackTop.get((i + j) / 2) + x);
          blackDown.set((n - 1 - i + j) / 2, blackDown.get((n - 1 - i + j) / 2) + x);
        } else {                // white
          whiteTop.set((i + j) / 2, whiteTop.get((i + j) / 2) + x);
          whiteDown.set((n - 1 - i + j) / 2, whiteDown.get((n - 1 - i + j) / 2) + x);
        }
      }
    }

    long maxWhite = -1;
    int IWhite = -1;
    int JWhite = -1;
    long maxBlack = -1;
    int IBlack = -1;
    int JBlack = -1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if ((i + j) % 2 == 1) {
          long tmp = blackTop.get((i + j) / 2) + blackDown.get((n - 1 - i + j) / 2) - table.get(i).get(j);
          if (tmp > maxBlack) {
            maxBlack = tmp;
            IBlack = i;
            JBlack = j;
          }
        } else {
          long tmp = whiteTop.get((i + j) / 2) + whiteDown.get((n - 1 - i + j) / 2) - table.get(i).get(j);
          if (tmp > maxWhite) {
            maxWhite = tmp;
            IWhite = i;
            JWhite = j;
          }
        }
      }
    }
    out.println(maxBlack + maxWhite);
    out.println((IWhite + 1) + " " + (JWhite + 1) + " " + (IBlack + 1) +  " " + (JBlack + 1));
  }

  private void start(String inputFile, String outputFile) throws FileNotFoundException {
    InputStream inputStream = new FileInputStream(inputFile);
    OutputStream outputStream = new FileOutputStream(outputFile);
    FastScanner in = new FastScanner(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    solve(in, out);
    out.close();
  }

  private void start(String inputFile) throws FileNotFoundException {
    InputStream inputStream = new FileInputStream(inputFile);
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    solve(in, out);
    out.close();
  }

  private void start() {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    solve(in, out);
    out.close();
  }

  public static void main(String[] args) throws FileNotFoundException {
    new Main().start();
  }


  class FastScanner {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public FastScanner(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String nextString() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(nextString());
    }

    public long nextLong() {
      return Long.parseLong(nextString());
    }

    public double nextDouble() {
      return Double.parseDouble(nextString());
    }
  }
}
