e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

Сума на матриці

Сума на матриці

Задано матрицю чисел aij, де 1in, 1jm. Для заданих lx, ly, rx, ry знайдіть

prb684

Вхідні дані

У першому рядку записано розміри матриці - n, m (1n, m1000). У наступних n рядках записано по m чисел aij (1aij1000), відокремлених пропуском. У n + 2 рядку записано число q (1q106) - кількість запитів. У наступних q рядках описано запити lxi, lyi, rxi, ryi (1lxirxin, 1lyiryim).

Вихідні дані

Виведіть q чисел в окремих рядках - відповіді на запити.

Ліміт часу 2 секунди
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
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
Вихідні дані #1
24
18
16
9
12
Автор В.Гольдштейн
Джерело Зимние сборы в Харькове 2010 День 2