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.*;
public class Gargari
{
   public static int n;
   public static int[][] array;
   public static void main(String[] args) throws IOException
   {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      n = Integer.parseInt(br.readLine());
      array = new int[n][n];
      for(int i = 0; i < n; i++)
      {
         String[] arr = br.readLine().split(" ");
         for(int j = 0; j < n; j++)
         {
            array[i][j] = Integer.parseInt(arr[j]);
         }
      }
      long[] negDiag = new long[2 * n - 1];
      long[] posDiag = new long[2 * n - 1];
      for(int i = 0; i < n; i++)
      {
         negDiag[i] = computation(0, n - 1 - i, 1);
         posDiag[i] = computation(0, i, -1);
      }
      for(int i = n; i < 2 * n - 1; i++)
      {
         negDiag[i] = computation(i - n + 1, 0, 1);
      }
      for(int i = n; i < 2 * n - 1; i++)
      {
         posDiag[i] = computation(i - n + 1, n - 1, -1);
      }
      long[][] value = new long[n][n];
      for(int i = 0; i < n; i++)
      {
         for(int j = 0; j < n; j++)
         {
            value[i][j] = negDiag[i + n - 1 - j] + posDiag[i + j] - array[i][j];
         }
      }
      long whiteMax = 0;
      long whiteMaxX = 0;
      long whiteMaxY = 0;
      long blackMax = 0;
      long blackMaxX = 0;
      long blackMaxY = 1;
      for(int i = 0; i < n; i++)
      {
         for(int j = 0; j < n; j++)
         {
            if((i + j) % 2 == 0)
            {
               if(value[i][j] > whiteMax)
               {
                  whiteMax = value[i][j];
                  whiteMaxX = i;
                  whiteMaxY = j;
               }
            }
            else
            {
               if(value[i][j] > blackMax)
               {
                  blackMax = value[i][j];
                  blackMaxX = i;
                  blackMaxY = j;
               }
            }
         }
      }
      whiteMaxX++;
      whiteMaxY++;
      blackMaxX++;
      blackMaxY++;
      System.out.println(blackMax + whiteMax);
      System.out.print(whiteMaxX + " " + whiteMaxY + " " + blackMaxX + " " + blackMaxY);

   }
   public static long computation(int x, int y, int dir)
   {
      long sum = 0;
      while(x < n && x >= 0 && y < n && y >= 0)
      {
         sum += array[x][y];
         x += 1;
         y += dir;
      }
      return sum;
   }
}