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.*;
import java.math.*;
 
public class Main {
 
    FastScanner in;
    PrintWriter out;
 
    static class FastScanner {
 
        BufferedReader br;
        StringTokenizer st;
 
        FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }
 
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        String nextLine() throws IOException {
            if (st == null || !st.hasMoreTokens())
                return br.readLine();
            StringBuilder result = new StringBuilder(st.nextToken());
            while (st.hasMoreTokens()) {
                result.append(" ");
                result.append(st.nextToken());
            }
            return result.toString();
        }
 
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
 
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
    }
 
    void run() throws IOException {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out, false);
        solve();
        out.close();
    }
 
    public static void main(String[] args) throws IOException{
        new Main().run();
    }
 
    public void printArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            out.print(arr[i] + " ");
        }
        out.println();
    }
 
    public long gcd(long a, long b){
        if(a == 0) return b;
        return gcd(b % a, a);
    }

    static int n;

    public void solve() throws IOException{

        int n = in.nextInt();
        long[][] bb = new long[n + 1][n + 1];
        long[] pd = new long[2 * n + 1];
        long[] sd = new long[2 * n + 1];

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                bb[i][j] = in.nextLong();
                pd[i - j + n] += bb[i][j];
                sd[i + j] += bb[i][j];
            }
        }

        List<long[]> res = new ArrayList<>();
        res.add(new long[]{-1, 0, 0});
        res.add(new long[]{-1, 0, 0});
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                long v = pd[i - j + n] + sd[i + j] - bb[i][j];
                long[] ele = res.get((i + j) & 1);
                long vOld = ele[0];
                if(vOld < v){
                    res.set( (i + j) & 1, new long[]{v, i, j});
                }
            }
        }

        out.println(res.get(0)[0] + res.get(1)[0]);
        out.println(res.get(0)[1] + " " + res.get(0)[2] + " " + 
                    res.get(1)[1] + " " + res.get(1)[2]);


    }
   
}