Дана карта освещённости в виде таблицы из r строк и c столбцов. В каждой клетке записана целая величина яркости.

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

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

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

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

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

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

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

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

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

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

Ограничения

• 1 <= r, c <= 1000
• -10^9 <= a_ij <= 10^9
• 1 <= q <= 2 * 10^5
• 1 <= r1 <= r2 <= r
• 1 <= c1 <= c2 <= c

Примеры

Пример 1

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

1 1
-5
3
1 1 1 1
1 1 1 1
1 1 1 1

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

-5
-5
-5

Пример 2

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

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

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

1
2
-5
3
-3
-3