2D Range Maximum Query

You are given a two-dimensional grid of integers. Your task is to process several queries where each query asks for the maximum value within a specified subrectangle of the grid. The subrectangle is defined by its top-left corner ((r_1, c_1)) and bottom-right corner ((r_2, c_2)) (both indices are 0-indexed).

A correct solution should build a data structure (such as a 2D segment tree) that allows for fast retrieval of the maximum element in any subrectangle. Specifically, for each query, you need to compute [ \max_{i=r_1}^{r_2} ; \max_{j=c_1}^{c_2} grid[i][j] ]

Efficient handling of both grid building and query processing is expected. Input is read from standard input and output is written to standard output.

inputFormat

The first line contains two integers (n) and (m) representing the number of rows and columns of the grid, respectively. The next (n) lines each contain (m) space-separated integers representing the grid. The following line contains an integer (q) denoting the number of queries. Each of the next (q) lines contains four space-separated integers (r_1), (c_1), (r_2), and (c_2) that describe a query for the maximum value in the subrectangle from ((r_1, c_1)) to ((r_2, c_2)).

outputFormat

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

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

8
9
9