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.util.*;
import java.io.*;

public class Gargari {
   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      long[][] grid = new long[n][n];
      for (int i = 0; i < n; i++) {
         String[] lol = br.readLine().split(" ");
         for (int j = 0; j < n; j++) {
            grid[i][j] = (long)(Integer.parseInt(lol[j]));
         }
      }
      long[] iup = new long[n];
      for (int i = 0; i < n; i++) {
         long sum = 0;
         for (int j = 0; j < i + 1; j++) {
            sum += grid[i - j][j];
         }
         iup[i] = sum;
      }
      long[] jup = new long[n - 1];
      for (int j = 1; j < n; j++) {
         long sum = 0;
         for (int i = 0; i < n - j; i++) {
            sum += grid[n - 1 - i][j + i];
         }
         jup[j - 1] = sum;
      }
      long[] idown = new long[n];
      for (int i = 0; i < n; i++) {
         long sum = 0;
         for (int j = 0; j < n - i; j++) {
            sum += grid[i + j][j];
         }
         idown[i] = sum;
      }
      long[] jdown = new long[n - 1];
      for (int j = 1; j < n; j++) {
         long sum = 0;
         for (int i = 0; i < n - j; i++) {
            sum += grid[i][j + i];
         }
         jdown[j - 1] = sum;
      }
      int ieven = 0;
      int iodd = 0;
      int jeven = 0;
      int jodd = 1;
      long val1 = 0;
      long val2 = 0;
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            if ((i + j) % 2 == 0) {
               long sum = 0; 
               if (i < j) {
                  sum += jdown[j - i - 1];
               }
               else {
                  sum += idown[i - j];
               }
               if (i + j < n) {
                  sum += iup[i + j];
               }
               else {
                  sum += jup[i + j - n];
               }
               sum -= grid[i][j];
               if (sum > val1) {
                  val1 = sum;
                  ieven = i;
                  jeven = j;
               }
            }
            if ((i + j) % 2 == 1) {
               long sum = 0; 
               if (i < j) {
                  sum += jdown[j - i - 1];
               }
               else {
                  sum += idown[i - j];
               }
               if (i + j < n) {
                  sum += iup[i + j];
               }
               else {
                  sum += jup[i + j - n];
               }
               sum -= grid[i][j];
               if (sum > val2) {
                  val2 = sum;
                  iodd = i;
                  jodd = j;
               }
            }
         }
      }
      System.out.println(val1 + val2);
      System.out.print(ieven + 1 + " ");
      System.out.print(jeven + 1 + " ");
      System.out.print(iodd + 1 + " ");
      System.out.print(jodd + 1);
   }
}