Iepure

Problema

Ai un șir de numere întregi $A$ de lungime $N$. Trebuie să răspunzi la $Q$ întrebări. Fiecare întrebare este de forma $(L,R)$, unde $L$ și $R$ sunt indecși din șir. Pentru fiecare întrebare, trebuie să calculezi suma elementelor din subșirul A[L \ldots R].

Intrare

• Prima linie conține două numere întregi $N$ și $Q$ (1 \leq N, Q \leq 10^5) — lungimea șirului și numărul de întrebări.

• A doua linie conține $N$ numere întregi A_1, A_2, \ldots, A_N (-10^9 \leq A_i \leq 10^9) — elementele șirului.

• Următoarele $Q$ linii conțin câte două numere întregi $L$ și $R$ (1 \leq L \leq R \leq N) — descrierea fiecărei întrebări.

Ieșire

Pentru fiecare întrebare, afișează suma elementelor din subșirul A[L \ldots R] pe o linie separată.