Tnia

Se dă o matrice binară cu $n$ coloane și $m$ linii. Coloanele sunt numerotate de la stânga la dreapta cu valori de la $1$ la $n$, iar liniile sunt numerotate de jos în sus cu valori de la $1$ la $m$.
Matricea dată are o formă particulară, astfel că pentru fiecare coloană $i$ de la $1$ la $n$ toate elementele matricei de pe coloana respectivă au valoarea 1 pentru toate liniile cuprinse în intervalul $[1,h[i]]$ și în rest valoarea $0$. Valorile $h[i]$ sunt numere naturale date în ordine crescătoare $(h[i-1] \leq h[i], 1 \leq i \leq n)$.

Cerință

Să se răspundă la $q$ întrebări de forma: dându-se numerele $A$, $B$, $C$, $D$ se cere suma elementelor din submatricea determinată de zona dreptunghiulară având colțul stânga-jos în coloana $A$ și linia $B$, iar colțul dreapta-sus în coloana $C$ și linia $D$.

Date de intrare

Fișierul de intrare este tnia.in.

• pe prima linie se găsesc două numere naturale $n$ și $m$ despărțite printr-un spațiu, cu semnificația de mai sus;
• pe a doua linie sunt cele $n$ elemente $h[i]$ ale vectorului despărțite prin câte un spațiu;
• pe a treia linie este un număr natural $q$ ce reprezintă numărul de întrebări;
• pe următoarele $q$ linii se găsesc câte 4 numere $A$, $B$, $C$, $D$ cu semnificația de mai sus, despărțite prin câte un spațiu.

Date de ieșire

Fișierul de ieșire tnia.out va conține $q$ linii reprezentând răspunsul pentru fiecare întrebare.

Restricții și precizări

• $0 \leq h[i] \leq m, 1 \leq n \leq 100 000$
• $1 \leq q \leq 100 000, 1 \leq m \leq 1 000 000 000$
• Pentru 15 puncte: $n, m, q \leq 100$
• Pentru alte 16 puncte: $n, m, q \leq 3000$
• Pentru alte 16 puncte: $n \leq 100 000, m \leq 1 000 000 000, q \leq 100$
• Se acordă 10 puncte pe exemplele din enunț.

Exemple

tnia.in

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

tnia.out

30 
6 
5 
0 
6

Explicație

Zona dreptunghiulară având colțul stânga-jos la coloana $1$ și linia $1$ și colțul dreapta-sus la coloana $5$ și linia $10$ are suma elementelor $30$. Analog, pentru celelalte patru întrebări, răspunsurile corecte sunt: $6$, $5$, $0$ și $6$.