/*

Strip of Land (IOI 1999)
Copyright (C) 2000 Sebastiano Vigna

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA




Per costruire un rettangolo massimale con variazione in altezza limitata,
scandiamo l'input riga per riga e manteniamo in maniera dinamica una matrice
M[i][d] che dice, per ogni colonna i, qual e` il numero massimo di righe di
cui si puo` salire mantenendo la variazione in altezza con l'elemento della
riga corrente nell'intervallo [0-d, C-d], con d=0,1,..,C.

La matrice e` mantenibile in maniera dinamica perche' a fronte di una
nuova riga e` sufficiente fare scorrere la lista di C+1 valori di M
corrispondenti a una colonna di un numero di posti uguale alla differenza
tra l'altezza corrente e quella precedente, e riempire il resto con uni
(lo scorrimento e` verso l'alto o verso il basso a seconda del segno della
differenza).

Una volta che la matrice e` riempita, per ogni larghezza l e` possibile
stabilire la massima altezza di un rettangolo che soddisfa i vincoli e sta
sopra alla riga corrente. Fissiamo una colonna i e un valore di d, e
supponiamo che il vettore a contenga le altezze della riga corrente. Sappiamo
di quanto possiamo al piu` salire nella colonna i mantenendo la variazione
in [0-d, C-d] andando a leggere M[i][d]. Poi ci spostiamo su i-1, andiamo a
vedere la massima ascesa possibile leggendo M[i][d+a[i-1]-a[i]] (sempre che
non debordiamo da M) e la minizziamo con quella corrente, e cosi` via. Si
noti che la condizione imposta implica che anche gli elementi nella colonna
i-1 saranno corretti, perche' le loro altezze saranno nell'intervallo

[a[i-1] - (d+a[i-1]-a[i]), a[i-i]+C - (d+a[i-1]-a[i])] = [a[i]-d, a[i]+C-d]

esattamente come quelli nella colonna i. Ogni volta massimizziamo l'area
del rettangolo ottenuto con quella corrente.

Se l'indice d+a[i-1]-a[i] deborda da M significa che l'altezza
dell'elemento nella colonna i-1 della riga corrente e` gia` al di fuori
dell'intervallo possibile di variazione, e quindi non e` possibile estendere
ulteriormente il rettangolo.

*/



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>

#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(x) ((x)<0?(-(x)):(x))


#define MAXC 10			/* Massima variazione in altezza */
#define MAXAMP 700		/* Massima ampiezza della mappa */
#define MAXALT 700		/* Massima altezza della mappa */
#define MAXAMPSOL 100	/* Massima ampiezza della soluzione */

int M[MAXAMP][MAXC+1];	/* Matrice riempita tramite programmazione dinamica */
int a[MAXAMP];	/* Altezze della riga corrente */

int main(int argc, char **argv) {
	int U, V, C, t, i, j, k, l, d, x1, x2, y, alt, altcorr;
	long maxArea;
	FILE *f;

	f = stdin;
	fscanf(f, "%d %d %d\n", &U, &V, &C);

	maxArea = 0;

   /* La matrice M viene inizialmente riempita di uni. */

   for(i=0; i<U; i++) for(j=0; j<=C; j++) M[i][j] = 1;

   /* Inoltre dobbiamo leggere la prima riga separatamente
   	e costruire il massimo sottosegmento con variazione
      limitata. */

	for(i=0; i<U; i++) {
		fscanf(f, "%d", &a[i]);
		for(d=0; d<=C; d++) { /* Variazione in [-d, C-d]. */
		/* Controlliamo i segmenti di lunghezza al piu` MAXAMSOL ed estremo
			destro in i */
			for(j=i; j>=0 && i-j<MAXAMPSOL; j--)
				if (a[j]-a[i] >= -d && a[j]-a[i] <= C-d) {
					if (maxArea < i-j+1) {
						maxArea = i-j+1;
						x1 = j;
						x2 = i;
						y = 0;
						alt = 1;
					}
				}
				else break;
		}
	}
	fscanf(f, "\n");

	for(l=1; l<V; l++) { 	/* Ora scandiamo le righe rimanenti. */
		for(i=0; i<U; i++) {
			fscanf(f, "%d", &t);
			if (abs(t-a[i])>C) /* Troppa variazione, resettiamo M a tutti uni. */
				for(j=0; j<=C; j++) M[i][j] = 1;
			else if (t>a[i]) {
				for(j=C; j>=t-a[i]; j--) M[i][j] = M[i][j-(t-a[i])]+1;
            for(; j>=0; j--) M[i][j] = 1;
			}
			else if (t<a[i]) {
				for(j=0; j<=C+(t-a[i]); j++) M[i][j] = M[i][j-(t-a[i])]+1;
            for(; j<=C; j++) M[i][j] = 1;
			}
			else for(j=0; j<=C; j++) M[i][j]++;

			a[i] = t;

			for(d=0; d<=C; d++) { /* Variazione in [-d, C-d]. */
				altcorr = INT_MAX;
				for(j=i; j>=0 && i-j<MAXAMPSOL; j--)
					/* Se la variazione non deborda dai limiti consentiti... */
					if (a[j]-a[i] >= -d && a[j]-a[i] <= C-d) {
						/* ...aggiorniamo l'altezza massima di un rettangolo
							con base [j,i] che soddisfa i vincoli... */
						altcorr = min(altcorr, M[j][d+a[j]-a[i]]);
						/* ...e se il rettangolo corrente e` piu` grande del
							migliore che abbiamo trovato finora, lo compriamo. */
						if (maxArea < (long)altcorr*(i-j+1)) {
							maxArea = (long)altcorr*(i-j+1);
							x1 = j;
							x2 = i;
							y = l;
							alt = altcorr;
						}
					}
					else break;
			}
		}
		fscanf(f, "\n");
	}

	f = stdout;

	/* Attenzione: le coordinate partono da UNO! */

	fprintf(f, "%d %d %d %d %ld\n", x1+1, y+1, x2+1, y+alt, maxArea);

	return 0;
}