Range Sum 1

Du har en lista med heltalen $A_0, A_1, \dots , A_{N-1}$.

Du ska svara på $Q$ stycken frågor ”beräkna $A_l+A_{l+1}+\cdots +A_{r}$”, där $l$ och $r$ är given för varje fråga.

Indata

Den första raden av indata innehåller två heltal $N, Q$ ($1 \leq N, Q \leq 2 \cdot 10^5$).

Nästa rad innehåller $N$ positiva heltal $A_0, A_1, \dots , A_{N-1}$ ($1 \leq A_i \leq 10^9$).

Därefter följer $Q$ rader, som vardera innehåller två heltal $L$ och $R$ ($0 \leq L \leq R \leq N-1$), intervallet för varje fråga.

Utdata

Skriv ut $Q$ rader som vardera innehåller ett heltal, svaret på motsvarande fråga.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall 1

I första frågan är $L=0$ och $R=3$. Därmed är svaret $A_0+A_1+A_2+A_3=1+4+3+1=9$.

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

9
5
4
7

3 1
1000000000 1000000000 1000000000
0 2

3000000000