Subsecvențe cu Suma Egală

Problema

Ai un șir de $n$ numere întregi, a_1, a_2, \ldots, a_n. Trebuie să răspunzi la $q$ întrebări. Fiecare întrebare îți oferă două numere întregi, $l$ și $r$, și îți cere să calculezi 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 100000) — numărul de elemente din șir și numărul de întrebări.

• A doua linie conține $n$ numere întregi a_1, a_2, \ldots, a_n (-1000 \leq a_i \leq 1000) — elementele șirului.

• Următoarele $q$ linii conțin câte două numere întregi $l$ și $r$ (1 \leq l \leq r \leq n) — limitele subșirului pentru fiecare întrebare.

Ieșire

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