Codeforces Round 371 (Div. 1) |
---|
Закончено |
Сова Соня подарила ёжику Филе огромный пазл размером 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
Название |
---|