Perete

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 este de forma: "Care este suma elementelor din șirul $a$ de la poziția $l$ la poziția $r$?"

Intrare

• Prima linie conține două numere întregi, $n$ și $q$ (1 \leq n, q \leq 100,000) — 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 de început și sfârșit pentru fiecare întrebare.

Ieșire

Pentru fiecare întrebare, afișează suma elementelor din șirul $a$ de la poziția $l$ la poziția $r$, inclusiv.