Задача №2772. Сумма в прямоугольнике
Необходимо набрать 12 баллов. A, В — 1 балл, С — 2 балла, D — 3 балла, E — 5 баллов
У Олега есть матрица целых чисел \(N \times M\). Его очень часто просят узнать сумму всех элементов матрицы в прямоугольнике с левым верхним углом (\(x_1\), \(y_1\)) и правым нижним (\(x_2\), \(y_2\)). Помогите ему в этом.
В первой строке находится числа \(N, M\) размеры матрицы (\(1 \leq N, M \leq 1000\)) и K - количество запросов (\(1 \leq K \leq 100000\)). Каждая из следующих \(N\) строк содержит по \(M\) чисел --- элементы соответствующей строки матрицы (по модулю не превосходят 1000). Последующие K строк содержат по \(4\) целых числа, разделенных пробелом - \(x_1\) \(y_1\) \(x_2\) \(y_2\) --- запрос на сумму элементов матрице в прямоугольнике (\(1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M\))
Для каждого запроса на отдельной строке выведите его результат - сумму всех чисел в элементов матрице в прямоугольнике \((x_1,y_1)\), \((x_2,y_2)\)
3 3 2 1 2 3 4 5 6 7 8 9 2 2 3 3 1 1 2 3
28 21