Дана карта освещённости размером r x c. В каждой клетке записана яркость соответствующего участка.

Необходимо обработать q запросов. Каждый запрос задаёт прямоугольный участок карты координатами (r1, c1, r2, c2) в нумерации с 1. Для каждого запроса требуется найти суммарную яркость всех клеток внутри этого прямоугольника, включая границы.

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

В первой строке даны два целых числа r и c — количество строк и столбцов карты.

В следующих r строках содержится по c целых чисел — значения яркости клеток карты.

Далее дано целое число q — количество запросов.

В следующих q строках записаны по четыре целых числа r1, c1, r2, c2, задающие прямоугольный участок.

Все данные подаются через стандартный ввод.

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

Для каждого запроса выведите одно целое число — суммарную яркость в соответствующем подпрямоугольнике.

Каждый ответ выводите в отдельной строке в стандартный вывод.

Ограничения

• 1 <= r, c <= 1000
• |a[i][j]| <= 10^9
• 1 <= q <= 2 * 10^5
• 1 <= r1 <= r2 <= r
• 1 <= c1 <= c2 <= c

Ответы могут не помещаться в 32-битный целочисленный тип.

Примеры

Пример 1

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

1 1
7
3
1 1 1 1
1 1 1 1
1 1 1 1

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

7
7
7

Пример 2

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

2 3
1 -2 3
-4 5 -6
5
1 1 1 1
1 1 2 3
1 2 2 2
2 1 2 3
1 3 2 3

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

1
-3
3
-5
-3