Земельный комитет
(Время: 5 сек. Память: 16 Мб Сложность: 41%)
Земельный комитет города принял решение о сдаче в аренду части муниципальной территории, имеющей форму прямоугольника размером H на W километров. Стоимость аренды каждого квадратного участка 1×1 км была определена с учётом локальных условий, и занесена в таблицу.
С целью организации открытого тендера на аренду, земельный комитет решил выставить на своём веб-сайте карту территории, и предоставить посетителям возможность узнавать суммарную стоимость аренды для произвольной прямоугольной группы соседних участков.
Данное предложение вызвало большой интерес у населения и предпринимателей, и нагрузка на сервер очень высока.
Требуется написать программу, позволяющую как можно более эффективно рассчитывать стоимость аренды для N запросов. В каждом запросе требуется определить общую стоимость участков внутри прямоугольной группы с противоположными углами, расположенными в элементах таблицы (ai, bi) и (ci, di).
Входные данные
В первой строке входного файла INPUT.TXT находятся числа H, W, N (1 ≤ H, W ≤ 100, 1 ≤ N ≤ 106). В следующих H строках содержится по W чисел (стоимости участков находятся в диапазоне от 0 до 10 000). Далее идут N строк с числами ai, bi, ci и di (1 ≤ ai ≤ ci ≤ H, 1 ≤ bi ≤ di ≤ W).
Выходные данные
В выходной файл OUTPUT.TXT должен содержать N чисел, по одному числу в строке.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 3 1
5 1 2
6 7 3
2 1 2 3
| 16 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
