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

Дан массив из \(N\) целых чисел. Вам поступают запросы о сумме всех элементов массива с элемента x по элемент y включительно. Требуется ответить на все запросы.

Входные данные

В первой строке находится число \(N\) количество элементов массива (1 ≤ \(N\) ≤ 100000) и \(M\) - количесто запросов(1 ≤ \(M\) ≤ 100000). В следующей строке через пробел указаны элементы массива (по модулю не превосходят 1000). Последующие M строк содержат по 2-а целых числа, разделенных пробелом - запрос на сумму элементов на отрезке массива (1 ≤ \(x\) ≤ \(y\) ≤ \(N\))

Выходные данные

Для каждого запроса на отдельной строке выведите его результат - сумму всех чисел в массиве от элемента x до элемента y.

Примеры

Входные данные

Выходные данные

9
12

Задача на informatics