лад представлен прямоугольной таблицей из r строк и c столбцов. Каждая ячейка либо занята, либо свободна. Если ячейка занята, в таблице стоит 1, иначе 0.

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

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

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

Первая строка содержит два целых числа r и c — количество строк и столбцов таблицы.

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

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

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

Ввод осуществляется через стандартный ввод.

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

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

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

Ограничения

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

Примеры

Пример 1

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

3 3
1 0 1
0 1 1
1 1 0
2
1 1 2 2
1 1 3 3

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

2
6

Пояснение

В прямоугольнике (1,1)-(2,2) две единицы; во всей матрице — шесть.

Пример 2

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

1 1
1
2
1 1 1 1
1 1 1 1

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

1
1