Прямокутні суми

Дано прямокутну таблицю розмірами ~N~ рядків на ~M~ стовпчиків, елементи якої є натуральними числами. Потрібно багатократно знаходити суми всіх чисел, що потрапляють у деякі прямокутники цієї таблиці, утворені рядками з ~i_1~-го по ~i_2~-й та стовпчиками з ~j_1~-го по ~j_2~-й (нумерація з 1, межі включно, ~{1 \leqslant i_1 \leqslant i_2 \leqslant N}~, нумерація рядків згори донизу, ~{1 \leqslant j_1 \leqslant j_2 \leqslant M}~, нумерація стовпчиків зліва направо).

Вхідні дані

У \mbox{1-му} рядку через одинарний пробіл записано числа ~N~ та ~M~, далі ~N~ рядків по ~M~ чисел у кожному містять значення комірок таблиці. Далі в окремому рядку записано число ~T~ — кількість подальших запитів, потім ще ~T~ рядків — самі запити, кожен у вигляді ~{i_1\,\,i_2\,\,j_1\,\,j_2}~ (через одинарні пробіли, ~{1 \leqslant i_1 \leqslant i_2 \leqslant N}~, ~{1 \leqslant j_1 \leqslant j_2 \leqslant M}~).

Результати

Рівно ~T~ рядків, кожен з яких містить єдине число — суму, що є відповіддю чергового запиту.

Приклади

Ввід

4 5
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
3
1 4 1 5
1 2 3 4
2 4 2 2

Вивід

90
16
12

Оцінювання

Оцінювання поблокове (бали за блок нараховуються лише в разі успішного проходження всіх тестів блоку); тест з умови є 1-м і входить у блок 1. Стовпчик «передумови» означає, що розв'язок запускатиметься і перевірятиметься на поточному блоці, лише якщо цей самий розв'язок успішно пройшов блоки, згадані в передумовах. Нерівності через кому (як-то «~{100 \leqslant N,M \leqslant 400}~») означають, що всі перелічені через кому змінні перебувають в указаному діапазоні. Обмеження на «~a_{ij}~» вказують можливі значення елементів таблиці.