T373870 [HOLD-R1] 营救

夜晚，行走在危机四伏的 RDFZ。从松柏林到灌木迷宫，四处都有巡逻的人影。

RDFZ 是一个 $N$ 行 $M$ 列的平面，坐标为 $(i,j)$ 的位置上的威胁值为 $W_{i,j}$。 你要从位于 $(x_{1},y_{1})$ 的地点出发，去营救位于 $(x_{2},y_{2})$ 的朋友。 每一步行走只能选择向上、下、左、右四个方向移动 $1$ 个单位。所到达的位置的威胁值必须**小于**等于你的体力值（且不超越边界），也就是说，当你经过一个坐标为 $(i,j)$ 的位置（包括起始与终止的两个位置）时，你的体力必须**大于等于**这个点的威胁值 $W_{i,j}$。 注意，体力值自身不会发生变化。 请你帮忙计算，为了成功营救你的朋友，你的体力至少应该是多少？

第一行三个整数 $N,M,Q$，其中 $Q$ 表示询问组数。 接下来一个 $N$ 行 $M$ 列的矩阵表示威胁值 $W_{i,j}$。 接下来 $Q$ 行，每行包含一组询问：四个整数 $x_1,y_1,x_2,y_2$，表示你的初始位置和你朋友被困的位置。

输出 $Q$ 行，对于每组询问：输出一行一个整数，表示你至少需要多少体力。

**数据范围：** 对于 $20\%$ 的数据：$Q\le 100$，$N, M\le 40$； 对于另外 $20\%$ 的数据：$Q\le 10^5$，$ N, M\le 20$； 对于 $100\%$ 的数据：$0\le W_{ij}\le 10^9$，$1\le Q\le 10^5$，$1\le N, M\le 40$。