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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class GargariAndBishops {
    public static void main(String[] args) {
            FastScanner fs=new FastScanner();
            int n=fs.nextInt();
            long[][] arr=new long[n+1][n+1];
            long[] upArrow = new long[2*n+1],downArrow = new long[2*n+1];
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    arr[i][j]=fs.nextInt();
                    upArrow[i+j]+=arr[i][j];
                    downArrow[n+i-j]+=arr[i][j];
                }
            }
            long brr[][] = new long[2][2];
            long ans[] = {-1,-1};
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    update((i+j)&1,i,j,upArrow[i+j]+downArrow[i-j+n]-arr[i][j],brr,ans);
                }
            }
            StringBuilder s = new StringBuilder();
            s.append(ans[0]+ans[1]).append('\n');
            s.append(brr[0][0]).append(' ').append(brr[0][1]).append(' ');
            s.append(brr[1][0]).append(' ').append(brr[1][1]);
        System.out.println(s);
        }
        static private void update(int c, int i, int j, long val,long[][] brr,long[] ans){
            if(ans[c]<val){
                ans[c]=val;
                brr[c][0]=i;
                brr[c][1]=j;
            }
        }

        static class FastScanner {
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st=new StringTokenizer("");
            String next() {
                while (!st.hasMoreTokens())
                    try {
                        st=new StringTokenizer(br.readLine());
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                return st.nextToken();
            }

            int nextInt() {
                return Integer.parseInt(next());
            }
            int[] readArray(int n) {
                int[] a=new int[n];
                for (int i=0; i<n; i++) a[i]=nextInt();
                return a;
            }
            long nextLong() {
                return Long.parseLong(next());
            }
        }
}
