Summat

Se consideră şirul crescător $1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,...$, în care fiecare număr natural nenul $i$ apare de $2^{i-1}$ ori. Elementele unui matrice $A$ cu $M$ linii şi $N$ coloane au valori astfel încât, parcurgând matricea de sus în jos, pe linii, și de la stânga la dreapta pe fiecare linie, se obțin primii $M\cdot N$ termeni ai șirului precizat.

De exemplu, dacă $M=5$ şi $N=8$, matricea este:

$$A= \begin{pmatrix} 1 & 2 & 2 & 3 & 3 & 3 & 3 & 4\\ 4 & 4 & 4 & 4 & 4 & 4 & 4 & 5\\ 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5\\ 5 & 5 & 5 & 5 & 5 & 5 & 5 & 6\\ 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 \end{pmatrix}$$

O submatrice a lui $A$ este definită de patru valori, $l_{1}, c_{1}, l_{2}, c_{2},\ (l_{1}\leq l_{2},\ c_{1}\leq c_{2})$ şi este formată din elementele $A_{i,j}$ cu proprietatea că $l_{1}\leq i\leq l_{2}$ şi $c_{1}\leq j\leq c_{2}$.

Cerință

Determinaţi suma elementelor pentru fiecare dintre $Q$ submatrice date ale lui $A$.

Date de intrare

Fişierul de intrare summat.in conţine pe prima linie numerele naturale nenule $M, N, Q$ cu semnificaţia din enunţ, iar pe următoarele Q linii câte patru numere naturale $l_{1}\ c_{1}\ l_{2}\ c_{2}$ care definesc câte o submatrice a lui $A$. Numerele aflate pe aceeaşi linie a fişierului sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire summat.out conţine pe Q linii sumele determinate pentru cele Q submatrice, câte un singur număr pe linie, în ordinea în care submatricele sunt definite în fişierul de intrare.

Restricții și precizări

• $1 \leq M,N \leq 100 \ 000 \ 000$;
• $1 \leq Q \leq 100 \ 000$;
• $1 \leq l_{1} \leq l_{2} \leq M$;
• $1 \leq c_{1} \leq c_{2} \leq N$.

Exemplu

summat.in

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

summat.out

24
100
62

Explicație

Matricea generată este cea din enunţ. Submatricele corespunzătoare celor trei cerinţe sunt date mai jos.

$$\begin{pmatrix} 1 & 2 & 2 & 3 \\ 4 & 4 & 4 & 4 \end{pmatrix}$$$$\begin{pmatrix} 4 & 4 & 4 & 4 & 4 \\ 5 & 5 & 5 & 5 & 5 \\ 5 & 5 & 5 & 5 & 5 \\ 6 & 6 & 6 & 6 & 6 \end{pmatrix}$$$$\begin{pmatrix} 3 & 3 & 3 & 3 & 4\\ 4 & 4 & 4 & 4 & 5\\ 5 & 5 & 5 & 5 & 5 \end{pmatrix}$$