### IOI '99 - Antalya-Belek, Turkey

## A Strip of Land

The residents of Dingilville are trying to locate a region
to build an airport. The map of the land is at hand. The map is a rectangular grid of unit
squares, each identified by a pair of coordinates (*x*,*y*), where *x* is
the horizontal (west-east) and *y* is the vertical (south-north) coordinate. The height of every square is shown on
the map.

Your task is to find a rectangular region of squares with the largest area (i.e. a rectangular region consisting of the largest number of squares) such that

- the height difference between the highest and the lowest squares of the region is less
than or equal to a given limit
*C*, and - the width (i.e. the number of squares along the west-east direction) of the region is at most 100.

In case there is more than one such region you are required to report only one of them.

### Input

The first line contains three integers: the number of squares in the east-west direction,*U*(1 ≤

*U*≤ 700), the number of squares in the north-south direction,

*V*(1 ≤

*V*≤ 700), and

*C*(0 ≤

*C*≤ 10).

Each of the following

*V*lines contains the integers

*H*

_{xy}(-30 000 ≤

*H*

_{xy}≤ 30 000) for

*x =*1,…,

*U*. More specifically,

*H*

_{xy}occurs as the

*x*

^{th}number on the (

*V*-

*y+2)*

^{th}input line.

### Output

The output should consist of a single line containing four space-separated integers describing the region found:*X*

_{min},

*Y*

_{min},

*X*

_{max},

*Y*

_{max}, where (

*X*

_{min},

*Y*

_{min}) are the coordinates of the southwest corner square, and (

*X*

_{max},

*Y*

_{max}) are the coordinates of the northeast corner square of the region.

### Sample Input

10 15 4 41 40 41 38 39 39 40 42 40 40 39 40 43 40 36 37 35 39 42 42 44 41 39 40 38 40 41 38 35 37 38 38 33 39 36 37 32 36 38 40 39 40 3939 39 40 40 4143 41 39 40 4138 39 38 39 3939 42 36 39 3939 39 40 39 4140 41 31 37 3641 41 40 39 4140 40 40 40 4042 41 40 39 3939 39 42 40 4440 38 40 39 3937 41 41 41 4039 39 40 41 4039 40 47 45 49 43 43 41 41 40 39 42 42 41 41 39 40 39 42 40 42 42 41 44 49 43 46 41 42 41 42 42 45 40 42 42 46 42 44 40 42 41

### Sample Output

4 5 8 11Note: the bolded region in the input map corresponds to the region indicated in the output.

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 5.00s

**Memory Limit:** 32M

**Added:** Aug 22, 2009

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

ryuugaon Jul 11, 2010 - 2:57:42 am UTC oopsthat explains and fixes it.

example worked both ways(it starts 5 above and below bottom/top), and I rarely see those coordinate systems

Still too slow for last 7 cases, but works for others

ryuugaon Jul 09, 2010 - 7:23:42 am UTCWhat does the judge check the answers against?

bbi5291on Jul 11, 2010 - 2:23:04 am UTC Re: ...I think that the judge is correct, and that you forgot that y-coordinates increase from bottom to top.