Дана прямоугольная матрица целых чисел размером M×N. Необходимо выполнить K операций вычисления суммы в прямоугольнике, принадлежащем исходной матрице, с координатами левого верхнего угла (x1,y1) и правого нижнего – (x2,y2).
В первой строке входного файла INPUT.TXT записаны 3 числа: N и M – число строк и столбцов матрицы (1 ≤ N, M ≤ 1000) и K - количество запросов (1 ≤ K ≤ 105). Каждая из следующих N строк содержит по M чисел - элементы Aij соответствующей строки матрицы (1 ≤ Aij ≤ 104). Последующие K строк содержат по 4 целых числа - y1, x1, y2 и x2 - запрос на сумму элементов в прямоугольнике (1 ≤ y1 ≤ y2 ≤ N, 1 ≤ x1 ≤ x2 ≤ M).
В выходной файл OUTPUT.TXT для каждого запроса в отдельной строке выведите результат суммы.
№ | INPUT.TXT | OUTPUT.TXT |
1 | 3 3 2
1 2 3
4 5 6
7 8 9
2 2 3 3
1 1 2 3 | 28 21 |