给定一个 $n\times m$ 的 $0/1$ 矩阵，有 $Q$ 组询问，每组询问给出一对 $(i,j)$ 和 $(x,y)$，询问在不超过这以两个点为对顶点（保证一个左上，一个右下）的长方形内最大的由 $1$ 构成的正方形的边长。

其中

$1\le n,m\le 1000$

$1\le Q \le 10^6$

---

赛时做法是预处理再用二维线段树维护区间最大值，然后二分答案询问，但是复杂度 $\mathcal{O}(n^2\log(n)+Q\log(n)^3)$ 左右，多了两个 $log$ 的样子....