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

Copyright (c) IARCS 2003-2020; Last Updated: 16 Jun 2006