Сервис обработки изображений хранит изображение в виде матрицы целых значений яркости размером n × m. Для анализа изображения массово поступают запросы: для каждой прямоугольной области нужно быстро вычислить суммарную яркость всех пикселей внутри неё.

Матрица яркости задана как a[1..n][1..m]. Каждый запрос описывается четырьмя числами r1, c1, r2, c2, где 1 <= r1 <= r2 <= n и 1 <= c1 <= c2 <= m.

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

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

Первая строка содержит три целых числа n, m, q — количество строк, количество столбцов и число запросов.

Следующие n строк содержат по m целых чисел в каждой — значения яркости a[i][j].

Следующие q строк содержат описания запросов, по четыре целых числа: r1, c1, r2, c2.

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

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

Ограничения

1 <= n, m <= 1000

1 <= q <= 100000

-10^9 <= a[i][j] <= 10^9

Примеры

Пример 1

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

2 2 5
1 2
3 4
1 1 1 1
1 1 1 2
2 2 2 2
1 2 2 2
1 1 2 2

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

1
3
4
6
10

Пример 2

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

1 5 6
123456789 -987654321 123456789 -987654321 123456789
1 1 1 1
1 1 1 5
1 2 1 4
1 3 1 3
1 5 1 5
1 1 1 3

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

123456789
-1604938275
-1851851853
123456789
123456789
-740740743