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

N Q
A[1] A[2] ... A[N]
L[1] R[1]
L[2] R[2]
...
L[Q] R[Q]

Date de ieșire

S[1]
S[2]
...
S[Q]

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$.