← 返回题目列表

Codeforces · 713/D

D. 动物和谜题

中文机器翻译题面 查看原题

猫头鹰索尼娅送给刺猬菲利亚一个大小为 n × m 的巨大湖拼图作为生日礼物。朋友们立即开始组装拼图,但结果发现拼图的某些部分是空的——上面没有图片。有图片的部分用 1 表示,空的部分用 0 表示。拼图的行从上到下用 1 到 n 的整数编号,而列从左到右用 1 到 m 的整数编号。

动物们决定完成图片并玩它,因为它可能会更有趣!猫头鹰和刺猬互相问一些问题。每个查询由定义矩形的四个整数 x1, y1, x2, y2 提供,其中 (x1, y1) 代表矩形左上单元格的坐标,而 (x2, y2) 代表右下单元格的坐标。查询的答案是仅由图片部分(仅用 1 表示的部分)组成且完全位于查询矩形内部的最大正方形的大小。

帮助索尼娅和菲利亚回答问题。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1000) — 拼图的大小。

以下 n 行每行包含 m 个整数 aij。如果相应的单元格包含图片,则它们每个都等于 1;如果相应的单元格为空,则每个单元格都等于 0。

下一行包含一个整数 t (1 ≤ t ≤ 1 000 000) — 查询数。

然后,t 行后面是查询的描述。它们每个都包含四个整数 x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m) - 查询矩形左上角和右下角单元格的坐标。

输出

打印 t 行。其中第 i 个应该包含由 1 组成且完全位于查询矩形内的正方形的最大大小。

示例

输入 #1

3 4
1 1 0 1
0 1 1 0
0 1 1 0
5
1 1 2 3
2 1 3 2
3 2 3 4
1 1 3 4
1 2 3 4

输出 #1

1
1
1
2
2