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.InputStream;
import java.io.FilterInputStream;
import java.util.NoSuchElementException;
import java.io.BufferedInputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.io.IOException;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Zyflair Griffane
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputUtil in = new InputUtil(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
    public void solve(int testNumber, InputUtil in, PrintWriter out) {
        int n = in.nextInt();
        long[] d1 = new long[n << 2];
        long[] d2 = new long[n << 2];
        long[][] arr = new long[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int x = in.nextInt();
                d1[j - i + n] += x;
                d2[i + j] += x;
                arr[i][j] = x;
            }
        }

        long[] res = new long[6];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int idx = (i + j) & 1;
                if (res[idx] <= d1[j - i + n] + d2[i + j] - arr[i][j]) {
                    res[idx] = d1[j - i + n] + d2[i + j] - arr[i][j];
                    res[idx * 2 + 2] = i + 1;
                    res[idx * 2 + 3] = j + 1;
                }
            }
        }
        out.println((res[0] + res[1]));
        out.println(res[2] + " " + res[3] + " " + res[4] + " " + res[5]);
    }
}

class InputUtil {

    JoltyScanner in;

    public InputUtil(InputStream istream) {
        in = new JoltyScanner(istream);
    }

    public String next() {
        return in.nextOrNull();
    }

    public Vector2D next2DVector() {
        return new Vector2D(in.nextDouble(), in.nextDouble());
    }

    public double nextDouble() { return in.nextDouble(); }

    public int nextInt() {
        String s = next();
        if (s == null) {
            throw new NoSuchElementException("Attempted to read integer that is not there.");
        }
        return Integer.parseInt(s);
    }

    public String nextLine() {
        return in.nextLine();
    }

    public long nextLong() {
        String s = next();
        if (s == null) {
            throw new NoSuchElementException("Attempted to read long that is not there.");
        }
        return Long.parseLong(s);
    }

    public String[] nextLineInTokens() { return in.nextLine().split("[\\s]+"); }

    public int[][] next2DIntArray(int rows, int cols) {
        int[][] arr = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        return arr;
    }

    public char[][] nextCharRows(int rows) {
        char[][] arr = new char[rows][];
        for (int i = 0; i < rows; i++) {
            arr[i] = in.next().toCharArray();
        }
        return arr;
    }

    public void nextDoubleArrays(double[]...arrays) {
        for (int i = 0; i < arrays[0].length; i++) {
            for (int j = 0; j < arrays.length; j++)
                arrays[j][i] = in.nextDouble();
        }
    }

    public int[] nextIntArray (int size) {
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = in.nextInt();
        }
        return arr;
    }

    public long[] nextLongArray(int size) {
        long[] arr = new long[size];
        for (int i = 0; i < size; i++) {
            arr[i] = in.nextLong();
        }
        return arr;
    }

    public void nextIntArrays(int[]...arrays) {
        for (int i = 0; i < arrays[0].length; i++) {
            for (int j = 0; j < arrays.length; j++)
                arrays[j][i] = in.nextInt();
        }
    }

    public CostGraph nextUndirectedCostGraph(int vertices, int edges) {
        return nextUndirectedCostGraph(vertices, edges, 0);
    }

    public CostGraph nextUndirectedCostGraph(int vertices, int edges, int delta) {
        CostGraph res = new CostGraph(vertices, edges << 1);
        for (int i = 0; i < edges; i++) {
            int u = in.nextInt() - delta;
            int v = in.nextInt() - delta;
            int cost = in.nextInt();
            res.addUndirectedEdge(u, v, cost);
        }
        return res;
    }

    public CostGraph nextUndirectedUnitCostGraph(int vertices, int edges) {
        CostGraph res = new CostGraph(vertices, edges << 1);
        for (int i = 0; i < edges; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            res.addUndirectedEdge(u, v, 1);
        }
        return res;
    }

    public char peekChar() {
        return in.peekChar();
    }
}

class JoltyScanner {
	// LOOK AT THAT SPEED. THAT SPEED.
	public static final int BASE_SPEED = 130;
	public static final int BUFFER_SIZE = 1 << 16;
	public static final char NULL_CHAR = (char) -1;

    BufferedInputStream in;
	StringBuilder str = new StringBuilder();
	byte[] buffer = new byte[BUFFER_SIZE];
	boolean EOF_FLAG = false;

    char c = NULL_CHAR;
	int bufferIdx = 0;
    int size = 0;

	public JoltyScanner(InputStream in) {
		this.in = new BufferedInputStream(in, BUFFER_SIZE);
	}

	public int nextInt() {
		long x = nextLong();
		if (x > Integer.MAX_VALUE || x < Integer.MIN_VALUE) {
			throw new ArithmeticException("Scanned value overflows integer");
		}
		return (int) x;
	}

	public long nextLong() {
		boolean negative = false;
		if (c == NULL_CHAR) {
			c = nextChar();
		}
		for (; !EOF_FLAG && (c < '0' || c > '9'); c = nextChar()) {
			if (c == '-') {
				negative = true;
			}				
		}
		checkEOF();
		long res = 0;
		for (; c >= '0' && c <= '9'; c = nextChar()) {
			res = (res << 3) + (res << 1) + c - '0';
		}
		return negative ? -res : res;
	}

	public String nextLine() {
		checkEOF();
		str.setLength(0);
		for (c = c == NULL_CHAR ? nextChar() : c; !EOF_FLAG && c != '\n'; c = nextChar()) {
			str.append(c);
		}
		c = NULL_CHAR;
		return str.toString();
	}

	public String next() {
		checkEOF();
		for (c = c == NULL_CHAR ? nextChar() : c; Character.isWhitespace(c); checkEOF()) {
			c = nextChar();
		}
		str.setLength(0);
		for (; !EOF_FLAG && !Character.isWhitespace(c); c = nextChar()) {
			str.append(c);
		}
		return str.toString();
	}

	public String nextOrNull() {
		try {
			return next();
		} catch (EndOfFileException e) {
			return null;
		}
	}

    public char peekChar() {
        if (c == NULL_CHAR) {
            c = nextChar();
        }
        return c;
    }

	public char nextChar() {
		if (EOF_FLAG) {
			return NULL_CHAR;
		}
		while (bufferIdx == size) {
			try {
				size = in.read(buffer);
				if (size == -1) {
					throw new Exception();
				}
			} catch (Exception e) {
				EOF_FLAG = true;
				return NULL_CHAR;
			}
			if (size == -1) {
				size = BUFFER_SIZE;
			}
			bufferIdx = 0;
		}
		return (char) buffer[bufferIdx++];
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
	
	public void checkEOF() {
		if (EOF_FLAG) {
			throw new EndOfFileException();
		}
	}

	public class EndOfFileException extends RuntimeException {
	}
}

class Vector2D {
    public static final double EPS = 1e-9;

    public final double x;
    public final double y;

    public Vector2D(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public Vector2D(double ang) {
        x = Math.cos(ang);
        y = Math.sin(ang);
    }

    public Vector2D add(Vector2D o) {
        return new Vector2D(x + o.x, y + o.y);
    }

    public double angle() {
        return Math.atan2(y, x);
    }

    public double ang(Vector2D o) {
        if (mag() == 0 | o.mag() == 0) {
            throw new ArithmeticException("Magnitude of one of the vectors is zero.");
        }
        return Math.acos(dot(o) / (mag() * o.mag()));
    }

    public boolean ccw(Vector2D v1, Vector2D v2) {
        return ((v1.x - x) * (v2.y - y) > (v2.x - x) * (v1.y - y));
    }

    public double cross(Vector2D o) {
        return x * o.y - y * o.x;
    }

    public double dist(Vector2D o) {
        return sub(o).mag();
    }

    public double dist2(Vector2D o) {
        return sub(o).mag2();
    }

    public double dot(Vector2D o) {
        return x * o.x + y * o.y;
    }

    public double mag() {
        return Math.sqrt(x * x + y * y);
    }

    public double mag2() {
        return x * x + y * y;
    }

    public Vector2D normalize() {
        double m = mag();
        if (m == 0) {
            return new Vector2D(0, 0);
        }
        return new Vector2D(x / m, y / m);
    }

    public boolean parallel(Vector2D o) {
        return Math.abs(cross(o)) <= EPS;
    }

    public Vector2D perp() {
        return new Vector2D(-y, x);
    }

    public Vector2D rotate(double ang) {
        return new Vector2D(x * Math.cos(ang) - y * Math.sin(ang), x * Math.sin(ang) + y * Math.cos(ang));
    }

    public Vector2D scale(double s) {
        return new Vector2D(x * s, y * s);
    }

    public Vector2D sub(Vector2D o) {
        return new Vector2D(x - o.x, y - o.y);
    }

    public String toString() {
        return "(" + x +"," + y + ")";
    }
}

class CostGraph extends SimpleGraph {

    public IntArrayList cost;

    public CostGraph(int vertexCount) {
        this(vertexCount, 16);
    }

    public CostGraph(int vertexCount, int edgeCount) {
        super(vertexCount, edgeCount);
        this.cost = new IntArrayList(edgeCount);
    }

    public int cost(int edge) {
        return cost.get(edge);
    }

    public IntArrayList edges(int u) {
        return edges[u];
    }

    public void addUndirectedEdge(int u, int v, int edgeCost) {
        addDirectedEdge(u, v, edgeCost);
        addDirectedEdge(v, u, edgeCost);
    }

    public void addDirectedEdge(int u, int v, int edgeCost) {
        super.addDirectedEdge(u, v);
        cost.add(edgeCost);
    }

}

class SimpleGraph {

    public IntArrayList to;
    public IntArrayList edges[];
    public int vertexCount;
    public int edgeCount;

    public SimpleGraph(int vertexCount) {
        this(vertexCount, 16);
    }

    public SimpleGraph(int vertexCount, int edgeCount) {
        this.to = new IntArrayList(edgeCount);
        this.edges = new IntArrayList[vertexCount];
        this.vertexCount = vertexCount;
        this.edgeCount = 0;
        for (int i = 0; i < vertexCount; i++) {
            edges[i] = new IntArrayList();
        }
    }

    public void addUndirectedEdge(int u, int v) {
        addDirectedEdge(u, v);
        addDirectedEdge(v, u);
    }

    public void addUndirectedEdges(int[] u, int[] v) {
        for (int i = 0; i < u.length; i++) {
            addDirectedEdge(u[i], v[i]);
            addDirectedEdge(v[i], u[i]);
        }
    }

    public void addDirectedEdges(int[] u, int[] v) {
        for (int i = 0; i < u.length; i++) {
            addDirectedEdge(u[i], v[i]);
        }
    }

    public void addDirectedEdge(int u, int v) {
        to.add(v);
        edges[u].add(edgeCount);
        edgeCount++;
    }

    public int to(int edge) {
        return to.get(edge);
    }

}

class IntArrayList implements Iterable<Integer> {
    int size = 0;
    int[] array;

    public IntArrayList() {
        this(16);
    }

    public IntArrayList(int length) {
        array = new int[length];
    }

    public <T extends Iterable<Integer>> IntArrayList(T intList) {
        this(16);
        addAll(intList);
    }

    public void add(int element) {
        ensureCapacity();
        array[size] = element;
        size++;
    }

    public <T extends Iterable<Integer>>void addAll(T intList) {
        for (int i: intList) {
            add(i);
        }
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("" + index);
        }
    }

    public void clear() {
        size = 0;
    }

    public void ensureCapacity() {
        if (size == array.length) {
            int[] newArray = new int[size << 1];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
    }

    public int get(int index) {
        checkIndex(index);
        return array[index];
    }

    public int indexOf(int value) {
        for (int i = 0; i < size; i++) {
            if (array[i] == value) {
                return i;
            }
        }
        return -1;
    }

    public void insert(int index, int value) {
        checkIndex(index);
        ensureCapacity();
        size++;
        for (int i = size; i > index; i--) {
            array[i] = array[i - 1];
        }
        array[index] = value;
    }

    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int index = 0;
            public boolean hasNext() {
                return index < size;
            }
            public Integer next() {
                return array[index++];
            }
            //FIXME - Never tested
            public void remove() {
                if (index == 0) {
                    throw new IndexOutOfBoundsException();
                }
                index--;
                System.arraycopy(array, index + 1, array, index, size - index);
                size--;
            }
        };
    }

    public int remove(int index) {
        checkIndex(index);
        int result = array[index];
        System.arraycopy(array, index + 1, array, index, size - 1 - index);
        size--;
        return result;
    }
    public void set(int index, int value) {
        checkIndex(index);
        array[index] = value;
    }
    public int size() {
        return size;
    }

    public String toString() {
        if (size == 0) {
            return "";
        }
        StringBuilder res = new StringBuilder();
        for (int i: this) {
            res.append(i);
            res.append(" ");
        }
        res.setLength(res.length() - 1);
        return res.toString();
    }

    public void trim() {
        int[] newArray = new int[size];
        System.arraycopy(array, 0, newArray, 0, size);
        array = newArray;
    }

    public int[] toArray() {
        int[] arrayCopy = new int[size];
        System.arraycopy(array, 0, arrayCopy, 0, size);
        return arrayCopy;
    }

    public void dec(int index) {
        checkIndex(index);
        array[index]--;
    }

    public void inc(int index) {
        checkIndex(index);
        array[index]++;
    }
}

