Matrix Sub-grid Maximum Query

Given an n×m matrix where each cell contains a non-negative integer representing the number of items in a warehouse, you need to answer multiple queries to determine the maximum number of items in a rectangular sub-grid. Each query provides the coordinates of the top‐left cell ((r_1, c_1)) and the bottom‐right cell ((r_2, c_2)) (with 1-indexing).

A suggested approach is to preprocess the matrix to build a 2D prefix maximum matrix (M) such that each cell (M_{i,j}) contains the maximum value from the sub-matrix spanning from the top-left corner ((1, 1)) to ((i, j)). However, you may also implement a direct query over the specified sub-grid if the input size permits.

Your program should read the grid and queries from standard input and output the results to standard output.

inputFormat

The first line of input contains two integers (n) and (m) separated by a space, representing the dimensions of the matrix. The next (n) lines each contain (m) integers, representing the matrix rows. The following line contains an integer (q), denoting the number of queries. Each of the next (q) lines contains four integers (r_1), (c_1), (r_2), (c_2) separated by spaces, defining a query for the sub-grid from ((r_1, c_1)) to ((r_2, c_2)).

outputFormat

For each query, output a single line containing the maximum number found in the specified sub-grid.## sample

3 3
1 3 2
4 6 5
7 3 9
2
1 1 2 2
2 2 3 3

6
9