Indian National Olympiad in Informatics

Related:

Online Programming Contest, 15-16 April 2006

IARCS home > OLYMPIAD

Basic Division

Problem 2: Mr Row and Mr Column, (K Narayan Kumar, CMI)

Mr Row and Mr Column are given a rectangular array of numbers. Mr Row can only read the array left-to-right, row by row, while Mr Column can only read the array top-to-bottom, column by column.

Mr Row and Mr Column are given two positions (i,j) and (k,l) and told to read all the numbers between these two positions. Mr Row starts at whichever position among (i,j) and (k,l) is earlier, row-wise, and proceeds row by row till he reaches the other position. Similarly, Mr Column starts at whichever position is earlier, column-wise, and proceeds column by column till he reaches the other position. In the process, some positions in the array are visited only by Mr Row, some are visited only by Mr Column and some are visited by both of them. The goal is to determine the maximum value in the array among all positions visited by Mr Row or Mr Column or both.

For example, suppose that the given array is

10  12  34  19 
18  11  17  39
41  27  12  19
40  19  21  50

and Mr Row and Mr Column are given the positions (4,2) and (2,3). Since (2,3) appears before (4,2), row-wise, Mr Row visits positions (2,3), (2,4), (3,1), (3,2), (3,3), (3,4), (4,1), (4,2). Similarly, since (4,2) appears before (2,3), column-wise, Mr Column visits positions (4,2), (1,3),(2,3). Among the positions visited by Mr Row and Mr Column, the largest value in the array is 41.

In this task, you will be a given an array of numbers along with K such pairs of positions. You should report the largest number among those visited by Mr Row or Mr Column for each such pair.

Input format

The first line contains two integers M and N giving the number of rows and columns in the rectangular grid. This is followed by M lines, each containing N integers, giving the elements of the grid. The next line, line M+2, contains a single integer K indicating the number of pairs of positions for which the maximum is to be computed. This is followed by K lines each containing four integers i, j, k and l, identifying two positions (i,j) and (k,l).

Output format

K lines of output each containing a single integer. The integer on line m should be the largest number encountered by either Mr Row or Mr Column when moving between the positions (i,j) and (k,l), where i, j, k and l are the numbers that appear on line M+2+m of the input.

Test data

You may assume that M, N ≤ 1000. You may also assume that K ≤ 10000.

Example

We now illustrate the input and output formats using the above example.

Sample input

4 4 
10 12 34 19 
18 11 17 39
41 27 12 19
40 19 21 50
2
4 2 2 3 
2 3 4 2

Sample output

41
41