Sumsubmat

Cerință

Fie o matrice $A$, cu $N$ linii și $M$ coloane și $Q$ query-uri de forma $x_{1}, y_{1}, x_{2}, y_{2}$. Pentru fiecare query se cere suma elementelor de pe conturul submatricei cu colțul stânga-sus $A_{x_{1}, y_{1}}$ și colțul dreapta-jos $A_{x_{2}, y_{2}}$, iar, dacă este pătratică, și elementelor de pe cele două diagonale.

Date de intrare

Fișierul de intrare sumsubmat.in conține:

• pe prima linie două numere naturale, $N$ și $M$, cu semnificația din enunț;
• pe următoarele $N$ linii $M$ numere naturale separate prin câte un spațiu;
• pe următoarea linie un număr natural, $Q$, cu semnificația din enunț;
• pe următoarele $Q$ linii patru numere naturale cu semnificația din enunț.

Date de ieșire

Pentru fiecare query afișează în sumsubmat.out pe câte o linie sumele cerute, fiecare pe câte o linie.

Restricții și precizări

• $1 \leq N, M \leq 1000$;
• $1 \leq A_{i, j} \leq 10^{9}$;
• $1 \leq Q \leq 3 \cdot 10^{6}$;

Exemplu

sumsubmat.in

3 3
1 2 3
1 3 2
3 2 1
1
1 1 3 3

sumsubmat.out

18