猫头鹰索尼娅送给刺猬菲利亚一个大小为 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