Cities in Alberta tend to be laid out as rectangular grids of blocks. Blocks are labeled with coordinates 0 to **R**-1 from north to south and 0 to **C**-1 from west to east.

The quality of living in each particular block has been ranked by a distinct number, called *quality rank*, between 1 and **R*****C**, where 1 is the best and **R*****C** is the worst.

The city planning department wishes to identify a rectangular set of blocks with dimensions **H** from north to south and **W** from west to east, such that the median quality rank among all blocks in the rectangle is the best. **H** and **W** are *odd* numbers not exceeding **R** and **C** respectively. The *median quality rank* among an odd number of quality ranks is defined to be the quality rank **m** in the set such that the number of quality ranks better than **m** equals the number of quality ranks worse than **m**.

You are to implement a procedure **rectangle(R,C,H,W,Q)** where **R** and **C** represent the total size of the city, **H** and **W** represent the dimensions of the set of blocks, and **Q** is an array such that **Q[a][b]** is the quality rank for the block labeled **a** from north to south and **b** from west to east.

Your implementation of **rectangle** must return a number: the best (numerically smallest) possible median quality rank of an **H** by **W** rectangle of blocks.

Each test run will only call **rectangle** once.

## Example 1

R=5,C=5,H=3,W=3,Q= 5 11 12 16 25 17 182 7 104 2320 3 124 2119 146 22 8 13 159

For this example, the best (numerically smallest) median quality rank of 9 is achieved by the middle-right rectangle of **Q **shown in bold. That is,

rectangle(R,C,H,W,Q)=9

## Example 2

R=2,C=6,H=1,W=5,Q= 6 1 2 11 7 5 9 3 4 10 12 8

For this example the correct answer is 5.

## Subtask 1 [20 points]

Assume R and C do not exceed 30.

## Subtask 2 [20 points]

Assume R and C do not exceed 100.

## Subtask 3 [20 points]

Assume R and C do not exceed 300.

## Subtask 4 [20 points]

Assume R and C do not exceed 1 000.

## Subtask 5 [20 points]

Assume R and C do not exceed 3 000.

## Implementation Details

- Use the RunC programming and test environment
- Implementation folder:
`/home/ioi2010-contestant/quality/`(prototype: quality.zip) - To be implemented by contestant:
`quality.c`or`quality.cpp`or`quality.pas` - Contestant interface:
`quality.h`or`quality.pas` - Grader interface:
*none* - Sample grader:
`grader.c`or`grader.cpp`or`grader.pas` - Sample grader input:
`grader.in.1``grader.in.2`etc.

*Note: The first line of input contains: R,C,H,W The following lines contain the elements of Q, in row-major order.* - Expected output for sample grader input:
`grader.expect.1``grader.expect.2`etc. - Compile and run (command line):
`runc grader.c`or`runc grader.cpp`or`runc grader.pas` - Compile and run (gedit plugin):
*Control-R*, while editing any implementation file. - Submit (command line):
`submit grader.c`or`submit grader.cpp`or`submit grader.pas` - Submit (gedit plugin):
*Control-J*, while editing any implementation or grader file.

Spoiler for: Solution | Show |
---|---|