Земельный комитет

Земельный комитет города принял решение о сдаче в аренду части муниципальной территории, имеющей форму прямоугольника размером H на W километров. Стоимость аренды каждого квадратного участка 1×1 км была определена с учётом локальных условий, и занесена в таблицу.

С целью организации открытого тендера на аренду, земельный комитет решил выставить на своём веб-сайте карту территории, и предоставить посетителям возможность узнавать суммарную стоимость аренды для произвольной прямоугольной группы соседних участков.

Данное предложение вызвало большой интерес у населения и предпринимателей, и нагрузка на сервер очень высока.

Требуется написать программу, позволяющую как можно более эффективно рассчитывать стоимость аренды для N запросов. В каждом запросе требуется определить общую стоимость участков внутри прямоугольной группы с противоположными углами, расположенными в элементах таблицы (a_i, b_i) и (c_i, d_i).

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

В первой строке входного файла INPUT.TXT находятся числа H, W, N (1 ≤ H, W ≤ 100, 1 ≤ N ≤ 10⁶). В следующих H строках содержится по W чисел (стоимости участков находятся в диапазоне от 0 до 10 000). Далее идут N строк с числами a_i, b_i, c_i и d_i (1 ≤ a_i ≤ c_i ≤ H, 1 ≤ b_i ≤ d_i ≤ W).

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

В выходной файл OUTPUT.TXT должен содержать N чисел, по одному числу в строке.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки]