Cerința

Intr-o gradina zoologica reprezentata printr-o matrice A cu n linii si m coloane. Fiecare cusca se afla intr-o pozitie din matrice si contine x animale. De exemplu daca A[2][6] = 5 inseamna ca in cusca de pe linia 2 si coloana 6 se afla 5 animale. Sa se raspunda la Q intrebari de forma i1, j1, i2, j2 unde raspunsul va fi numarul de animale din dreptunghiul din matrice cu cordonatele coltului din stanga sus i1 si j1 si cordonatele coltului din dreapta jos i2 si j2, unde i reprezinta linia si j coloana.

Date de intrare

Fișierul de intrare zoo.in conține pe prima linie numerele n si m, separate printr-un spatiu, iar pe urmatoarele n linii, cate m numere, reprezentand matricea. Pe linia n + 2 se afla numarul Q, iar pe urmatoarele Q linii, cate 4 numere (i1 j1 i2 j2) cu semnificatia din enunt.

Date de ieșire

Fișierul de ieșire zoo.out pe fiecare linie i raspunsul la intrebarea i.

Restricții și precizări

• 1 ≤ n, m ≤ 100
• 1 ≤ Q ≤ 100000
• numarul maxim de animale dintr-o cusca este de 1.000.000.000
• numerotarea liniilor si a coloanelor din matrice incepe de la 1

Exemplu

zoo.in

4 4
1 2 4 1
8 1 3 2
3 1 2 2
8 1 3 1
2
2 2 4 4
3 1 4 3

zoo.out

16
18

Explicație

16=1+3+2+1+2+2+1+3+1 si 18=3+1+2+8+1+3

#include <bits/stdc++.h>
using namespace std;

ifstream cin("zoo.in");
ofstream cout("zoo.out");

long long n , m , a[105][105] , s[105][105] , p , i1 , i2 , j1 , j2;

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            cin >> a[i][j];
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];

    cin >> p;
    for(int i = 1 ; i <= p ; i++)
    {
        cin >> i1 >> j1 >> i2 >> j2;
        cout << s[i2][j2] - s[i1-1][j2] - s[i2][j1-1] + s[i1 - 1][j1 - 1]<< '\n';
    }
}