U283470 被人找茬的走方格

在平时做题时，我们应该都接触过经典的走方格问题：给定 $n\times m$ 矩阵，从左上角 $(1,1)$ 走到右下角 $(n,m)$ 。除了起点和终点之外，其他方格都有对应的权值。我们可以每次往右走一格或者往下走一格，求可以获得的最大权值。 今天小 Z 和 小 Q 也要来走方格了，但是小 Z 想故意找茬，小 Q 见状，也想来故意找小 Z 的茬。

小 Z 希望把走方格想获得最大权值，改为走方格想获得最小权值。 小 Q 提出要求，需要对于一个固定的方格地图，**做多次求解**，每一次小 Q 会给定该方格中的一个子矩阵，**这个子矩阵内的所有点都是不可以经过的。** 需要注意的是，这可能会包括起点和终点。小 Q 希望小 Z 对于每次求解，给出是否可以到达终点的判断，如果能到达终点，那么可以获得的最小权值是多少。

每组评测点有一组数据。 第一行是三个以空格分隔的整数 $n,m,q$ ，表示方格矩阵为 $n$ 行 $m$ 列，做 $q$ 次查询。 接下来 $n$ 行，每行 $m$ 个非负整数，表示 $a_{i,j}$ 的权值。保证 $0\le a_{i,j}\le 10^9$ ，且 $a_{1,1}=a_{n,m}=0$ 。 再接下来 $q$ 行，每行四个以空格分隔的整数 $x_1,y_1,x_2,y_2(1\le x_1\le x_2\le n,1\le y_1\le y_2\le m)$ ，表示每次查询中选择了以 $(x_1,y_1)$ 为左上角， $(x_2,y_2)$ 为右下角的子矩阵（包含边界的方格），这些方格都不能走。

输出 $q$ 行。 对于每次查询，如果可以到达终点，输出可以获得的最小权值，否则输出 $-1$ 。

### 样例 1 解释 对于样例 1 , 原方格矩阵为 $$ \begin{pmatrix} 0&1&2\\ 3&4&5\\ 6&7&0\\ \end{pmatrix} $$ 对于第一次查询，有： $$ \begin{pmatrix} \color{red}0&\color{red}1&\color{red}2\\ \times&\times&\color{red}5\\ 6&7&\color{red}0\\ \end{pmatrix} $$ 最小权值为 $8$ 。 对于第二次查询为： $$ \begin{pmatrix} \times&\times&2\\ \times&\times&5\\ 6&7&0\\ \end{pmatrix} $$ 起点被封锁，无法到达终点，故返回 $-1$ 。 对于第三次查询为： $$ \begin{pmatrix} 0&\times&2\\ 3&\times&5\\ 6&\times&0\\ \end{pmatrix} $$ 第二列被封锁，无法到达终点，故返回 $-1$ 。 ## 数据范围 对于 $30\%$ 的数据有：$2\le n,m\le 100,q\le 10$ 。 对于 $100\%$ 的数据有：$2\le n,m\le 200,q\le 5\times 10^4$ 。