A93485.Animals and Puzzle

猫头鹰 Sonya 将一个 $n\times m$ 的湖拼图给刺猬 Filya，当做他的生日礼物。小伙伴们当即去组装这个拼图，然而有一些部分是空的——在那上面没有图片。

令有图片部分的贡献为 $1$，没有的为 $0$。对这个拼图编号，行号从上到下为 $1\sim n$ ，列号从左到右为 $1\sim m$$(1 \le n, m \le 1000) 。$

动物决定继续完成这个拼图，因为它可能更有趣。猫头鹰和刺猬会做出几组询问，每次给出四个整数 $x_1,y_1,x_2,y_2$ ，询问以 $(x_1,y_1)$ 为左上角，$(x_2,y_2)$ 为右下角的区域内，全为 $1$ 的最大正方形的边长。

第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个为 $0$ 或 $1$ 的整数，$1$ 表示有图片，$0$ 表示没有图片。

再一行一个整数 $t$ ，表示 $t$ 组询问。$(1 \le t \le 1000000)$

最后$t$ 行，每行四个整数分别表示 $x_1,y_1,x_2,y_2$。

共 $t$ 行，每行 $1$ 个整数，表示区域内最长大的全 $1$ 正方形的边长。