CF713D.Animals and Puzzle

Owl Sonya gave a huge lake puzzle of size n × m to hedgehog Filya as a birthday present. Friends immediately started to assemble the puzzle, but some parts of it turned out to be empty — there was no picture on them. Parts with picture on it are denoted by 1, while empty parts are denoted by 0. Rows of the puzzle are numbered from top to bottom with integers from 1 to n, while columns are numbered from left to right with integers from 1 to m.

Animals decided to complete the picture and play with it, as it might be even more fun! Owl and hedgehog ask each other some queries. Each query is provided by four integers _x_1, _y_1, _x_2, _y_2 which define the rectangle, where (_x_1, _y_1) stands for the coordinates of the up left cell of the rectangle, while (_x_2, _y_2) stands for the coordinates of the bottom right cell. The answer to the query is the size of the maximum square consisting of picture parts only (only parts denoted by 1) and located fully inside the query rectangle.

Help Sonya and Filya answer t queries.

猫头鹰索尼娅送给刺猬菲利娅一个尺寸为 $n \times m$ 的巨型湖景拼图作为生日礼物。朋友们立刻开始拼装这个拼图，但其中一些部分却是空的——上面没有图案。有图案的部分用 1 表示，空的部分用 0 表示。拼图的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。

动物们决定补全图案并一起玩耍，因为这样可能更有趣！猫头鹰和刺猬会互相提出若干查询。每个查询由四个整数 $x_1, y_1, x_2, y_2$ 给出，定义了一个矩形区域：$(x_1, y_1)$ 表示该矩形左上角单元格的坐标，$(x_2, y_2)$ 表示右下角单元格的坐标。查询的答案是：完全位于该查询矩形内部、且仅由图案部分（即全为 1 的单元格）构成的最大正方形的边长。

请帮助索尼娅和菲利娅回答 $t$ 个查询。

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 1000) — sizes of the puzzle.

Each of the following n lines contains m integers a__ij. Each of them is equal to 1 if the corresponding cell contains a picture and 0 if it's empty.

Next line contains an integer t (1 ≤ t ≤ 1 000 000) — the number of queries.

Then follow t lines with queries' descriptions. Each of them contains four integers _x_1, _y_1, _x_2, _y_2 (1 ≤ _x_1 ≤ _x_2 ≤ n, 1 ≤ _y_1 ≤ _y_2 ≤ m) — coordinates of the up left and bottom right cells of the query rectangle.

输入的第一行包含两个整数 $n$ 和 $m$（$1 ≤ n, m ≤ 1000$）——拼图的尺寸。

接下来的 $n$ 行中，每行包含 $m$ 个整数 $a_{ij}$。若对应单元格中包含图像，则该值为 $1$；若为空，则为 $0$。

下一行包含一个整数 $t$（$1 ≤ t ≤ 1\,000\,000$）——查询次数。

随后是 $t$ 行，每行描述一个查询：包含四个整数 $x_1$, $y_1$, $x_2$, $y_2$（$1 ≤ x_1 ≤ x_2 ≤ n$, $1 ≤ y_1 ≤ y_2 ≤ m$）——查询矩形的左上角与右下角单元格的坐标。

Print t lines. The i-th of them should contain the maximum size of the square consisting of 1-s and lying fully inside the query rectangle.

输出 $t$ 行。其中第 $i$ 行应包含完全位于第 $i$ 个查询矩形内部、且仅由 1 组成的最大正方形的边长。