Cerința

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

Restricții și precizări

• Se recomanda 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} \)

Subtask-uri

• 20 puncte: 1 ≤ N, Q ≤ 500
• 10 puncte: 1 ≤ N, Q ≤ 2.500
• 20 puncte: 1 ≤ N, Q ≤ 50.000
• 50 puncte: 1 ≤ N, Q ≤ 500.000

Formatul input-ului

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

Formatul output-ului

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

Exemplu:

Intrare

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

Iesire

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.