Сечење

Проблема:

Дадена е низа од $n$ цели броеви, a_1, a_2, \ldots, a_n. Потребно е да одговорите на $q$ прашања. Секое прашање е од обликот: дадени се два индекси $l$ и $r$, и треба да се пресмета збирот на сите елементи од низата од индексот $l$ до индексот $r$, вклучително.

Влез:

• Првата линија содржи два цели броја $n$ и $q$ (1 \leq n, q \leq 100000) — бројот на елементи во низата и бројот на прашања.

• Втората линија содржи $n$ цели броеви a_1, a_2, \ldots, a_n (-1000 \leq a_i \leq 1000) — елементите на низата.

• Следните $q$ линии содржат по два цели броја $l$ и $r$ (1 \leq l \leq r \leq n) — индекси кои го одредуваат опсегот за секое прашање.

Излез:

За секое прашање, испечатете го збирот на елементите од низата од индексот $l$ до индексот $r$.