Заданий двовимірний масив з \(N\) рядків та \(M\) стовпчиків.
Вам потрібно ефективно відповідати на запити \(R1\) \(C1\) \(R2\) \(C2\) - що означає порахувати суму всіх чисел рядки яких лежать на відрізку \([R1..R2]\), а стовпчики на відрізку \([C1..C2]\)

Формат вхідних даних

В першому рядку задані два цілих числа \(N\), \(M\) - розміри масиву.(\(1 \le N,M \le 1000\))
В наступних \(N\) рядках міститься по \(M\) чисел \(Aij\) - значення елементів масиву (\(1 \le Aij \le 1000\)).
В наступному рядку число \(Q\) - кількість запитів. (\(1 \le Q \le 10^6\))
В кожному з наступних \(Q\) рядків міститься чотири числа \(R1,C1,R2,C2\) що позначаюють запит (\(1 \le R1 \le R2 \le N\) , \(1 \le C1 \le C2 \le M\))

Формат вихідних даних

Для кожного запиту в окремому рядку виведіть відповідь

Приклад вхідних даних

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

Приклад вихідних даних

24
18
16
9
12