Maximum Height on Shortest Path

You are given a grid of integers where each cell represents the height at that cell. You are also given several queries. Each query consists of two points: a starting cell and a destination cell. Your task is to determine the maximum height encountered along the shortest path from the starting cell to the destination cell.

The grid is navigated with moves in the four cardinal directions (up, down, left, right). The shortest path is defined as the path with the minimum number of moves. In cases where there are multiple shortest paths, the one that minimizes the maximum cell height encountered is not required; instead, simply output the maximum height using the first reached shortest path via a Breadth-First Search (BFS).

Mathematically, the distance between two cells with coordinates \((x_1,y_1)\) and \((x_2,y_2)\) is given by:

$$\text{distance} = |x_1 - x_2| + |y_1 - y_2|.$$

inputFormat

The first line contains two integers n and m indicating the number of rows and columns of the grid.

The next n lines each contain m space-separated integers representing the grid.

The following line contains an integer q representing the number of queries.

Each of the next q lines contains four integers x1, y1, x2, y2 which represent the starting cell and the destination cell. Note that the cells are given in 1-indexed format.

outputFormat

For each query, output a single line containing the maximum height encountered along the shortest path from the starting cell to the destination cell.

## sample

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

6
7
8

</p>