Remote Training on Programming

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

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

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

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

Технические требования:

Входной файл: INPUT.TXT

Выходной файл: OUTPUT.TXT

Ограничение по времени тестирования: 1 секунда на один тест.

Формат входных данных:

В первой строке входного файла находятся числа H, W, N (1 ≤ H, W ≤ 100, 1 ≤ N ≤ 1 000 000). В следующих 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).

Формат выходных данных:

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

Пример файлов входных и выходных данных: