Ограничения: время – 1500ms/3000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
До появления Элли в стране жевунов Страшила жил посреди большого прямоугольного поля и пугал ворон.
Поле Страшилы состоит из одинаковых квадратных участков и имеет размеры `N xx M`. На каждом участке
выращивается `с_{ij}` сельскохозяйственных культур по принципу севооборота: первая культура выращивается в первый год,
вторая - во второй, ..., `c_{ij}`-я культура - в `c_{ij}`-ый, а в `(c_{ij}+1)`-ый год участок пустует для восстановления плодородия,
затем всё повторяется: первая культура - `(c_{ij}+2)`-ый год и так далее. Некоторые участки не возделываются (`c_{ij}=0`).
Кроме фермерства, жевуны очень любят праздники. Для каждого из праздников они занимают подходящий (для каждого праздника - свой)
прямоугольный кусок поля и ставят на нем шатры и аттракционы. Но чтобы не терять урожай, все занятые под празднование участки
должны в соответствующий год пустовать. Определите, как скоро жевуны смогут провести каждый из праздников.
В первой строке ввода указаны три натуральных числа: `N` и `M` - размеры поля (`1<=N,M <= 200`), `Q` - количество праздников (`Q <= 10^6`).
Затем следует `N` строк по `M` чисел в каждой - схема поля. Каждый участок описывается одним целым числом `c_{ij}` (`0<=c_{ij}<=40`) - количеством культур,
выращиваемых на нем.
Затем следует `Q` строк по 4 целых числа в каждой - описания частей поля, необходимых для проведения каждого
из праздников: `i_1, j_1` - координаты поля, находящегося в верхнем левом углу нужной территории, `i_2, j_2` - координаты поля
в правом нижнем углу (`1<=i_1<=i_2<=N`, `1<=j_1<=j_2<=M`).
Выведите `Q` натуральных чисел, по одному для каждого из праздников: минимальный номер года,
в который все соответствующие участки будут свободны.
```sample Пример ввода
2 5 3
3 1 2 0 1
0 0 5 0 0
2 1 2 2
1 4 2 5
1 1 2 5
```
```sample Пример вывода
1
2
12
```
Пояснение к примеру.\
В первом случае, оба требуемых участка всегда пустуют и их можно занять в первый же год.\
Во втором случае, единственный возделываемый участок (1,5) будет занят в первый год и освободится во второй.\
В третьем случае, в каждый из первых 11 лет хотя бы один из участков поля будет занят. На 12 год все участки освободятся.
Начало
Рабочее место участника
Алгоритм Эвклида