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 C{

    public static void main(String args[]){
        FastScanner in = new FastScanner(System.in);
        int n = in.nextInt();
        long[][] chess = new long[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                chess[i][j] = in.nextLong();
            }
        }
        long[] x = new long[2 * n - 1];
        long[] y = new long[2 * n - 1];
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                x[i - j + n - 1] += chess[i][j];
                y[i + j] += chess[i][j];
            }
        }
        
        long [][] ans = new long[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                ans[i][j] += x[i - j + n - 1];
                ans[i][j] += y[i + j];
                ans[i][j] -= chess[i][j];
            }
        }
        
        long ansx = 0;
        long ansy = 0;
        long max = 0;
        long ansx2 = 0;
        long ansy2 = 1;
        long max2 = 0;
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++){
                if((i + j) % 2 == 0 && ans[i][j] > max){
                    ansx = i;
                    ansy = j;
                    max = ans[i][j];
                }
                else if((i + j) % 2 == 1 && ans[i][j] > max2){
                    ansx2 = i;
                    ansy2 = j;
                    max2 = ans[i][j];
                }
            }
        }
        ansx++;
        ansy++;
        ansx2++;
        ansy2++;
        System.out.println(max2 + max);
        System.out.println(ansx2 + " " + ansy2 + " " + ansx + " " + ansy);
    }
    
    static class FastScanner{
        private BufferedReader reader;

        private StringTokenizer tokenizer;

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

        public String nextLine(){
            try{
                return reader.readLine();
            } catch(IOException e){
                e.printStackTrace();
                return null;
            }
        }

        public String next(){
            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(next());
        }

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

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