Сумма на отрезке

Дан массив из $n$ целых чисел и $q$ запросов. Для каждого запроса найдите сумму $a_l + a_{l+1} + \ldots + a_r$.

В первой строке $n$ и $q$ ($1 \le n, q \le 2 \cdot 10^5$). Во второй — целых чисел (). В каждой из следующих строк запрос: два целых числа и ().

Для каждого запроса в отдельной строке одно число — сумма.

Суммирование циклом в каждом запросе — $O(nq)$, это $4 \cdot 10^{10}$ операций. Посчитайте один раз префиксные суммы $p_i = a_1 + \ldots + a_i$ (), тогда каждый ответ — за .