P13664 「TPOI-5C」mαtrixing ωiθ μ

**本题禁止卡评测。** 

在东京的大雨后，天野阳菜给了 kele7 一个 $n$ 行 $m$ 列的矩阵 $A$。从上往下第 $i$ 行，从左往右第 $j$ 列的元素被称为 $A_{i,j}$。 kele7 喜欢删除矩阵。对于一个 $r$ 行 $c$ 列的矩阵 $B$，他会对它执行两种操作，同时会用**优雅值**衡量一个操作的优雅程度： - 删除矩阵的某一行 $B_{i,1},\dots,B_{i,c}$，优雅值为 $\text{mex}_{j=1}^cB_{i,j}$。然后将第 $i+1\sim r$ 行往上平移一行，令 $r\leftarrow r-1$。 - 删除矩阵的某一列 $B_{1,i},\dots,B_{r,i}$，优雅值为 $\text{mex}_{j=1}^rB_{j,i}$。然后将第 $i+1\sim c$ 列往左平移一列，令 $c\leftarrow c-1$。 最终 kele7 要将矩阵内的元素全部删除（即 $r$ 或 $c$ 变为 $0$）。定义一种删除方案 $S$ 的权值 $f(S)$ 为其中所有操作的优雅值的**最小值**。定义矩阵 $B$ 的权值 $F(B)$ 为所有删除它的方案 $S$ 中 $f(S)$ 的**最大值**。 kele7 把这个题目给了 lzyqwq。lzyqwq 觉得还可以加上 $q$ 次查询，每次给出 $x_1,y_1,x_2,y_2$，你需要回答当矩阵 $B$ 为矩阵 $A$ 以 $A_{x_1,y_1}$ 为左上角元素、$A_{x_2,y_2}$ 为右下角元素的子矩阵时，$F(B)$ 的值。 一个集合 $M$ 的 $\operatorname{mex}(M)$ 定义为最小的没有在 $M$ 中出现的自然数。如 $\text{mex}\{1,2,3,4\}=0,\text{mex}\{0,1,3,4\}=2$。

第一行三个正整数 $n,m,q$。 接下来 $n$ 行，每行 $m$ 个自然数。第 $i$ 行为 $A_{i,1},\dots,A_{i,m}$。 接下来 $q$ 行，每行四个整数 $x_1,y_1,x_2,y_2$ 表示一组询问。

$q$ 行，每行一个自然数，表示一个询问的答案。

**【样例解释】** 以第一个询问为例。初始矩阵 $B$ 为： $$\begin{bmatrix}0&1&0&1&2\\3&2&0&1&4\\5&4&3&0&1\\0&2&0&3&1\\0&0&0&1&2\end{bmatrix}$$ 一种可行的删除方案如下。 先删除第二行，优雅值为 $5$，得到新的矩阵 $B$ 为： $$\begin{bmatrix}0&1&0&1&2\\5&4&3&0&1\\0&2&0&3&1\\0&0&0&1&2\end{bmatrix}$$ 再删除第二列，优雅值为 $3$，得到新的矩阵 $B$ 为： $$\begin{bmatrix}0&0&1&2\\5&3&0&1\\0&0&3&1\\0&0&1&2\end{bmatrix}$$ 再依次删除所有行，优雅值分别为 $3,2,2,3$。 因此这种删除方案的权值为 $2$。可以证明，不存在优雅值的最小值更大的删除方案，因此答案为 $2$。 **【数据范围】** |$\text{Subtask}$|$n,m$ |$q$ |特殊性质 |分值 | |:--------:|:--------:|:--------:|:--------:|:--:| |$0$ |$n\times m\le3\times10^5$|$q=1$ |无 |$11$| |$1$ |$\color{red}{n,m\le300}$|$q\le10^5$|^ |^ | |$2$ |$n\times m\le10^5$|^ |^ |$20$| |$3$ |$n\times m\le2\times10^5$|$q\le2\times10^5$|^ |$24$| |$4$ |$n\times m\le3\times10^5$|$q\le3\times10^5$|$x_1=y_1=1$|$8$ | |$5$ |^ |^ |无 |$26$| 对于 $100\%$ 的数据，满足 $1\le n\times m,q\le 3\times 10^5$，$0\le A_{i,j}\le 10^9$。