Разминирование
Разминирование
После боевых действий возникла необходимость разминирования местности. Известно, что местность представлена прямоугольным участком размером n на m, на котором могут находиться мины. Количество мин, находящееся в соответствующем секторе местности представляется целым числом xij (0 ≤ xij ≤ 109).
Военные с помощью квадрокоптера делают снимки местности. Помогите сосчитать количество мин, которые попадают на снимки с квадрокоптера, если известно, что квадрокоптер делает k прямоугольных снимков этой местности.
Входные данные
В первой строке заданы два натуральных числа n и m (1 ≤ n, m ≤ 1000) - количество строк и столбцов соответственно.
Следующие n строк содержат m целых чисел xij (0 ≤ xij ≤ 109) - количество мин в соответствующем секторе.
В следующей строке записано число k (1 ≤ k ≤ 1000) - количество снимков с квадрокоптера.
Далее в k строках записаны координаты прямоугольных снимков (по четыре числа): y1, y2, x1, x2, где
y1 - номер строки, в которой начинается снимок,
y2 - номер строки, в которой снимок заканчивается,
x1 - номер столбца, в котором снимок начинается,
x2 - номер столбца, в котором снимок заканчивается.
Выходные данные
Выведите одно число - общее количество мин, которые попадут на снимки. Мины, присутствующие на нескольких снимках, учитываются один раз.
6 7 1 8 9 1 6 9 2 0 3 6 5 3 4 7 8 6 4 7 2 9 1 7 5 7 1 7 8 7 2 3 8 4 4 5 3 6 5 0 8 6 9 7 3 1 1 2 4 3 5 2 4 4 6 3 7
127