H. Horse Racing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Royal Bangkok Sports Club is preparing new endurance training for special horses. The racecourse is an $$$n × m$$$ grid of rectangular fields. Each field $$$(i, j)$$$ has a difficulty rating $$$D_{i,j}$$$. A higher value means the road there is rougher and requires more effort from the horse. Some fields are soft grass, while others are bumpy and uneven, demanding very high effort. Horses can move between two fields if they share a common side (up, down, left, and right).

For training, the committee designs tasks as follows:

  • A horse starts from a given field $$$(r, c)$$$.
  • It must visit every field inside a specified rectangular region $$$[r_1..r_2] \times [c_1..c_2]$$$ (including both boundaries) at least once.
  • The area of the specified rectangular region is at most $$$100$$$ fields.

The effort of a training route is defined as the maximum difficulty among all fields the horse must step on during the route.

The horse may choose any order to visit the fields, and the committee only cares about the minimum possible effort. There are $$$q$$$ tasks, and you must report all of them!

Input

The first line contains three integers $$$n, m, q$$$ $$$(1 \leq n, m \leq 500)$$$ and $$$(1 \leq q \leq 10^5)$$$.

The next $$$n$$$ lines each contain $$$m$$$ integers, giving the difficulty ratings $$$D_{i,j}$$$ of the fields.

  • $$$1 \leq i \leq n$$$ and $$$1 \leq j \leq m$$$
  • $$$0 \leq D_{i,j} \leq 10^9$$$

Each of the next q lines describes one query with six integers $$$r, c, r_1, c_1, r_2, c_2$$$

  • $$$1 \leq r \leq n$$$ and $$$1 \leq c \leq m$$$
  • $$$1 \leq r_1 \leq r_2 \leq n$$$
  • $$$1 \leq c_1 \leq c_2 \leq m$$$
  • It is guaranteed that $$$1 \leq (r_2 - r_1 + 1) \cdot (c_2 - c_1 + 1) \leq 100$$$
Output

For each query, print a single integer — the minimum effort required for that horse's route.

Example
Input
3 4 2
5 1 7 7
6 4 2 8
9 3 3 3
2 2 1 2 2 3
1 1 2 2 3 3
Output
7
5
Note

These are the moves that results in the minimum cost.

Other routes may exist, but whichever path is chosen, the minimum possible effort should be the same.