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).

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.

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.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 2005
using namespace std;
typedef long long LL;
int num[N][N];
LL sumN[N*2], sumM[N*2];

int n;

int main()
{
    while(scanf("%d", &n)!=EOF)
    {
        memset(sumN, 0, sizeof(sumN));
        memset(sumM, 0, sizeof(sumM));
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
            {
                scanf("%d", &num[i][j]);
                sumN[i+j]+=num[i][j];//横纵坐标之和为i+j的对角线的数值和
                sumM[i-j+n]+=num[i][j];//横纵坐标之差为i-j的对角线的数值和
            }

        LL max1=-1, max2=-1, s;
        int x1, x2, y1, y2;
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
            {
                if((i+j)&1)
                {
                    if(max1<(s=sumN[i+j]+sumM[i-j+n]-num[i][j]))
                    {
                        max1=s;//横纵坐标之和为奇数并且获得对角线上数值最大的格子
                        x1=i;
                        y1=j;
                    }
                }
                else
                {
                    if(max2<(s=sumN[i+j]+sumM[i-j+n]-num[i][j]))
                    {
                        max2=s;//横纵坐标之和为偶数并且获得对角线上数值最大的格子
                        x2=i;
                        y2=j;
                    }
                }
            }

        printf("%lld\n",max1+max2);
        printf("%d %d %d %d\n", x1, y1, x2, y2);
    }
    return 0;
}