D. Зверята и пазл
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сова Соня подарила ёжику Филе огромный пазл размером n на m с изображением красивого озера. Друзья сразу начали собирать картинку, но много фрагментов пазла оказались пустыми — на них не было никакого рисунка. Фрагменты с рисунком будем обозначать числом 1, а пустые фрагменты — числом 0. Строки пазла пронумерованы сверху вниз целыми числами от 1 до n, а столбцы — слева направо целыми числами от 1 до m.

Зверята решили сложить картину полностью и немного поиграть с ней, ведь это же еще интереснее! Сова и ёжик по очереди задают друг другу вопросы. Вопрос определяется четырьмя числами x1, y1, x2, y2, которые описывают прямоугольник, где (x1, y1) — координаты левой верхней клетки прямоугольника, а (x2, y2) — координаты правой нижней клетки. Ответом на вопрос является максимальный размер квадрата, полностью сложенного из фрагментов с рисунками (то есть квадрата из 1) и полностью находящегося внутри прямоугольника из вопроса.

Помогите Соне и Филе ответить на t запросов.

Входные данные

В первой строке входных данных записаны два числа n и m (1 ≤ n, m ≤ 1000) — размеры пазла.

В каждой из последующих n строк записаны m чисел aij. Каждое число равно 1, если в соответствующей клетке пазла есть рисунок, и 0, если она пустая.

В следующей строке записано целое число t (1 ≤ t ≤ 1 000 000) — количество запросов.

Дальше идут t строк, которые описывают запросы, i-я из этих строк содержит четыре числа x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m) — координаты левой верхней и правой нижней клеток прямоугольника-запроса.

Выходные данные

Выведите t строк. В i-й из них выведите максимальную длину стороны квадрата, полностью состоящего из 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
2
2