SumOfAll

Cerință

Se dă un vector de $N$ numere naturale. Se dau de asemenea $Q$ query-uri de forma $[l, r]$, unde se cere suma tuturor subsecvențelor de elemente consecutive. Mai formal, pentru fiecare query $[l, r]$, se cere rezultatul funcției $F(l, r) = \sum_{i=l}^{r} \sum_{j=i}^{r} S(i, j)$, unde $S(l, r)$ este suma tuturor elementelor din secvența $[l, r]$.

Date de intrare

Pe prima linie se citesc două numere întregi $N$ și $Q$.

Pe a doua linie, se citește un vector $A$ cu $N$ elemente. Elementele acestui vector sunt separate prin spațiu.

Pe următoarele $Q$ linii, se citesc perechi de numere întregi $l$ și $r$, care definesc o subsecvență în vectorul $A$.

Date de ieșire

Pentru fiecare dintre cele $Q$ query-uri, se afișează pe o linie separată rezultatul.

Restricții și precizări

• Se recomandă folosirea fastio.
• $1 ≤ N, Q ≤ 500\ 000$
• $0 ≤ A[i] ≤ 1\ 000\ 000\ 000$
• $1 ≤ l ≤ r ≤ N$
• Deoarece răspunsurile sunt prea mari pentru a fi reprezentate de tipurile de date implicite din limbajul C++, se vor afișa modulo ${2}^{32}$.

Exemplu

stdin

5 4
5 3 2 4 2
3 4
3 5
4 5
1 5

stdout

12
28
12
109

Explicație

Pentru primul query (secvența $[3, 4]$), suma este $2 + 4 + (2 + 4) = 12$.

Pentru al doilea query (secvența $[3, 5]$), suma este $2 + 4 + 2 + (2 + 4) + (4 + 2) + (2 + 4 + 2) = 28$.

Pentru al treilea query (secvența $[4, 5]$), suma este $4 + 2 + (4 + 2) = 12$.

Pentru al patrulea query (secvența $[1, 5]$), suma este $5 + 3 + 2 + 4 + 2 + (5 + 3)$ $+\ (3 + 2) + (2 + 4) + (4 + 2) + (5 + 3 + 2)$ $+\ (3 + 2 + 4) + (2 + 4 + 2) + (5 + 3 + 2 + 4) + (3 + 2 + 4 + 2)$ $+\ (5 + 3 + 2 + 4 + 2) = 109$.