Maximum Value in Subgrid

Given a grid of integers and several queries, each query asking for the maximum element in a specified subgrid, compute the maximum value for each query.

The subgrid is described by its top-left corner \( (x_1, y_1) \) and bottom-right corner \( (x_2, y_2) \) (using 1-indexed positions). For each query, you must find the maximum element in the rectangular area defined by these coordinates.

For example, if the query is \( (1,1,2,3) \), you should consider all the values in the rows 1 to 2 and columns 1 to 3, then output the maximum found.

inputFormat

The input begins with two integers \( n \) and \( m \) representing the number of rows and columns of the grid, respectively.

Then follow \( n \) lines, each containing \( m \) space-separated integers representing the grid values.

The next line contains an integer \( q \), the number of queries.

Each of the following \( q \) lines contains four integers \( x_1 \), \( y_1 \), \( x_2 \), and \( y_2 \) that specify a query, where \( (x_1, y_1) \) is the top-left corner and \( (x_2, y_2) \) is the bottom-right corner of the subgrid.

outputFormat

For each query, output a single line containing the maximum value found in the specified subgrid.

4 5
1 2 3 4 5
5 3 -1 6 7
8 9 10 11 12
13 14 15 16 17
3
1 1 2 3
2 2 4 5
3 1 4 2

5
17
14