Tăiere

Problema

Ai un șir de numere întregi a_1, a_2, \ldots, a_n. Trebuie să răspunzi la $q$ întrebări, fiecare întrebare fiind de forma: "Care este suma elementelor din subșirul a_l, a_{l+1}, \ldots, a_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) — indicii subșirului pentru care trebuie să calculezi suma.

Ieșire

Pentru fiecare întrebare, afișează suma elementelor din subșirul a_l, a_{l+1}, \ldots, a_r pe o linie separată.