/* This works. Mesh approach, mono-directional, position is given
     This works     l          j
           -----------------------------------
           |        |          |             |
           |        |          |             |
    i+j-k  -----------------------------------
           |        |       |  |             |
           |        |       |_ |             |
           |        |          |             |
         i -----------------------------------
           |        |          |             |
           |        |          |             |
           -----------------------------------

At time k, 
   s[i][j] is sum of a[i+j-k .. i][1 .. j]
   min[i][j] is minimum of s[i+j-k .. i][1 .. l] for l=1,..,j
   c[i][j] is column sum of a[i+j-k .. i][j]
   max[i][j] is maximum sum of a[i+j-k][l .. j] for l=1,...,j
*/
#include <stdio.h>
struct position{
  int x1; int y1; int x2; int y2;
};
int a[100][100], c[100][100], s[100][100];
int a1[100][100], c1[100][100], s1[100][100];
int min[100][100]; int max[100][100];
int min1[100][100]; int max1[100][100];
int minindex[100][100]; int minindex1[100][100];
int control[100][100];
int control1[100][100];
int i,k,j,m,n,r; int sol; 
struct position solindex[100][100];
struct position pos;
out(int a[100][100]){
int i, j;
for(i=1;i<=n;i++){
  for(j=1;j<=n;j++)printf("%3d",a[i][j]);
  printf("\n");
} }
copyback(int a[100][100], int a1[100][100]){
int i,j;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)a[i][j]=a1[i][j];
}
renewsol(struct position *pos, int i, int j, int k){
  solindex[i][j].x2=i; solindex[i][j].y2=j;
  (*pos).x1=i+j-k; (*pos).y1=minindex1[i][j]+1;
  (*pos).x2=i; (*pos).y2=j;
}
main(){
scanf("%d",&n);
random(); random(); random();
for (i=1;i<=n; i++)
for (j=1;j<=n; j++){
  r=random()%3;
  printf("%d ", r);
  if(r==2)a[i][j]=-1; else a[i][j]=r;
}
//a[1][1]=-3;
printf("\n");
for (i=1;i<=n; i++){
  for (j=1;j<=n; j++) printf("%3d ", a[i][j]);
  printf("\n");
}
for(i=0;i<=n;i++)for(j=0;j<=n;j++)control[i][j]=0;
  for (i=1;i<=n; i++)
    for (j=1;j<=n; j++){
      c[i][0]=0; c[0][j]=0;
      min[i][0]=0; max[i][0]=0;
      control[i][0]=1;
      minindex[i][0]=0;
    } 
sol=-99;
for(k=1;k<=2*n-1;k++){
  for (i=1;i<=n; i++)
    for (j=1;j<=n; j++){
      if(control[i][j-1]==1){
      c1[i][j]=c[i-1][j]+a[i][j];
      s1[i][j]=s[i][j-1]+c1[i][j];

      if(s1[i][j]<min[i][j-1])
             {min1[i][j]=s1[i][j]; minindex1[i][j]=j;} 
        else {min1[i][j]=min[i][j-1]; minindex1[i][j]=minindex[i][j-1];}

      if(s1[i][j]-min1[i][j]>max[i][j-1])max1[i][j]=s1[i][j]-min1[i][j]; 
                                    else max1[i][j]=max[i][j-1];
      if(max1[i][j]>sol){
        renewsol(&pos,i,j,k);
        sol=max1[i][j]; printf("k,i,j,sol= %d %d %d %d",k,i,j,sol); getchar();}
      control1[i][j]=1;
      }
    }
  copyback(s,s1); copyback(c,c1);  copyback(control,control1);
  copyback(min,min1); copyback(max,max1); copyback(minindex, minindex1); 
//  getchar(); printf("control=\n"); out(control);
  getchar(); printf("m=\n"); out(min);
  getchar(); printf("s=\n"); out(s);
} /*** k ***/
  printf("sol= %d x1 %d y1 %d x2 %d y2 %d\n",sol, pos.x1, pos.y1, pos.x2, pos.y2);
}