Сумма на квартале

В городе сетка кварталов размера H×W. В каждом квартале записано число — насколько там “шумно” сегодня (может быть отрицательным: значит, там стало тише).

Мэрия задаёт много вопросов вида: «Каков общий шум на прямоугольном районе?» Район всегда задаётся двумя углами и включает все кварталы внутри.

Важно: сумма по району может не помещаться в 32-битный тип (как на некоторых языках), ориентируйтесь на 64-битные значения. В Python это не проблема.

Формат ввода

Первая строка: два целых числа H и W (1 ≤ H ≤ 250, 1 ≤ W ≤ 250). Далее H строк по W целых чисел a[i][j] (−10^6 ≤ a[i][j] ≤ 10^6). Затем целое число Q (1 ≤ Q ≤ 4000). Далее Q строк: r1 c1 r2 c2 — координаты прямоугольника (1 ≤ r1 ≤ r2 ≤ H, 1 ≤ c1 ≤ c2 ≤ W). Прямоугольник включает все клетки с строками от r1 до r2 и столбцами от c1 до c2.

Формат вывода

Выведите Q строк. В i-й строке — сумму чисел в указанном прямоугольнике.

Ограничения

H, W ≤ 250, Q ≤ 4000. Значения в клетках от −10^6 до 10^6.

Пример

Ввод:

3 4
1 2 3 4
-5 0 7 1
2 2 2 2
2
1 1 2 3
2 2 3 4

Вывод:

8
14

Ключевое наблюдение: если уметь быстро находить сумму в прямоугольнике от (1,1) до (r,c), то любой запросный прямоугольник можно собрать из четырёх таких сумм (принцип «включил-исключил»).

Приём: 2D префиксные суммы. Строим таблицу ps, где ps[r][c] — сумма всех клеток в прямоугольнике с углами (1,1) и (r,c). Тогда сумма любого района (r1..r2, c1..c2) считается за константное время.

План решения:

• Создай ps размером (H+1)×(W+1), заполни нулями (дополнительная нулевая строка и столбец упрощают границы).
• Пройди по клеткам (r=1..H, c=1..W) и посчитай префиксы. Удобная формула:
• ps[r][c] = ps[r-1][c] + ps[r][c-1] - ps[r-1][c-1] + a[r][c]

(можно ускорить, накапливая сумму по строке).

• Для каждого запроса используй включение-исключение:
• sum = ps[r2][c2] - ps[r1-1][c2] - ps[r2][c1-1] + ps[r1-1][c1-1]
• Выведи ответы.

Сложность: построение O(H*W), каждый запрос O(1), всего O(H*W + Q) по времени и O(H*W) по памяти.

Частая ошибка: перепутать знаки в формуле запроса или забыть сделать ps с «нулевой рамкой», из-за чего ломаются случаи с r1=1 или c1=1.