Minimum Element in Submatrix

You are given an n × m matrix consisting of positive integers. Your task is to process a number of queries. Each query gives you a submatrix specified by its top-left and bottom-right coordinates (x₁, y₁) and (x₂, y₂), and you need to determine the minimum element in that submatrix.

Formally, you are given a matrix A with dimensions n × m and q queries. For each query, find: [ min{ A_{i,j} \mid x₁ \le i \le x₂,; y₁ \le j \le y₂ }] where indices are 1-based.

Note: All input values are positive, and submatrix queries are always valid within the matrix.

inputFormat

Input is read from standard input (stdin).

The first line contains two integers n and m, representing the number of rows and columns respectively.

The next n lines each contain m integers separated by spaces, representing the rows of the matrix.

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

Then q lines follow, each containing four integers x₁, y₁, x₂, and y₂, describing a submatrix query.

outputFormat

Output to standard output (stdout). For each query, print a single line containing the minimum element in the specified submatrix.## sample

5 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
3
1 1 3 3
2 2 4 4
1 3 5 5

1
7
3