Problem G
Veður

Image from commons.wikimedia.org

As often before there is now a blue dotted weather warning in the capital area so people need to be cautious when out and about. The met office’s supercomputer blew away so people need help planning their routes.

The wind forecast for the capital area can be represented by a two-dimensional grid where each cell contains the wind speed in that cell. Since the weather is so bad people are fine with taking longer routes than usual, they just want to get to their destination in the least windy way possible. People can travel between adjacent cells on the map (up, down, left and right but not diagonally) and people want to take the route that minimizes the highest wind speed encountered along the way.

Before the supercomputer blew away everyone had found out what route they would take, but the info on the highest wind speed encountered along the way was lost. Since people want to know how well prepared they need to be this has to figured out.

Input

The first line of the input contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^5)$, the height and width of the map. Furthermore $1 \leq n \cdot m \leq 10^5$ will hold.

Then there are $n$ lines, each with $m$ integers $v_{i,j}$ ($1 \leq v_{i,j} \leq 10^{18}$), denoting the wind speed in the cell in row $i$ and column $j$ of the map.

Next there is a single line with an integer $q$ ($1 \leq q \leq 10^5$) giving the number of individuals who need to know the highest wind speed they will encounter.

Finally there are $q$ lines each containing four integers $l_1, d_1, l_2, d_2$ ($1 \leq l_1, l_2 \leq n$ and $1 \leq d_1, d_2, \leq m$). This denotes a query for the highest wind speed someone will encounter when moving from the cell in row $l_1$ and column $d_1$ to the cell in row $l_2$ and column $d_2$.

Output

For each query in the input, print a single line with an integer giving the highest wind speed that person will have to endure if they choose their route optimally.

Scoring

3 4
3 4 2 2
9 9 9 8
1 1 1 3
4
3 1 3 3
1 1 3 1
1 1 1 4
2 2 2 2

1
8
4
9