Юниорская олимпиада по информатике 2022 года за 8 класс | Казахстанские олимпиады

Задача B. Квадрат

Дан двумерный массив $n$, $m$. Где все элементы массива либо $0$ либо $1$.

Вам надо ответить на $q$ запросов. Каждый запрос содержит $4$ числа $x_1,y_1,x_2,y_2$, которые являются координаты прямоугольника. $(x_1,y_1)$ - координаты левой верхней клетки прямоугольника, a $(x_2,y_2)$ - координаты правой нижней клетки. Для каждого запроса вам нужна найти максимальный размер квадрата который содержит только $1$ и полностью находящегося внутри прямоугольника.

Формат входного файла

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

В каждой из последующих $n$ строк записаны $m$ чисел $a_{i,j}$. $(0 \leq a_{i,j} \leq 1)$

В следующей строке записано количество запросов $q$. $(1 \leq q \leq 5 * 10^5)$

После идут $q$ строк сами запросы $x_1,y_1,x_2,y_2$. $(1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq m)$

Формат выходного файла

Выведите $q$ строк. Ответ на каждый запрос.

Примеры

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

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

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

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

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

2
2
2