Max Height in Submatrices

You are given a matrix of integers representing heights. Your task is to answer multiple queries efficiently. Each query asks for the maximum value within a submatrix defined by its top-left and bottom-right coordinates. The indices are given in 1-indexed format. Formally, for a query with coordinates (l_1, r_1, l_2, r_2), you need to find the maximum value in the submatrix consisting of rows (l_1) to (l_2) and columns (r_1) to (r_2).

Input constraints are as described in the input section. Your solution should read from standard input (stdin) and write the results to standard output (stdout).

inputFormat

The first line contains three space-separated integers (N), (M), and (Q), representing the number of rows, columns, and queries respectively. The next (N) lines each contain (M) space-separated integers representing the matrix. Each of the following (Q) lines contains four space-separated integers (l_1), (r_1), (l_2), and (r_2) that describe a query.

outputFormat

Output (Q) lines, each containing a single integer, where the integer is the maximum value found in the submatrix for the corresponding query.## sample

4 5 3
1 2 3 4 5
5 10 5 10 5
3 2 1 2 3
4 4 4 4 4
1 1 2 3
2 2 4 4
1 1 4 5

10
10
10