Городские олимпиады/1-2 курсы/Предметная олимпиада по информатике 2019


5. Считай ещё быстрее (100 баллов)

Автор задачи: Комаров Вячеслав
Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Скоро состоится Галактическая олимпиада сумм, и Слава тренирует Таню для выступления на ней.

Для тренировки Слава использует массив, состоящий из n целых чисел. Он задаёт ей вопросы следующего вида — необходимо назвать сумму чисел в массиве с l-го по r-й (включая границы).

Таня настолько быстро называет ответ на каждый вопрос, что Слава сам не успевает посчитать его. Поэтому он просит помощи у Вас. Помогите Славе, посчитайте ответ на каждый из его вопросов.

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

Первая строка входных данных содержит два целых числа: n и q количество чисел в массиве и количество вопросов (1 \leqslant n,q \leqslant 10^{5}).

В следующей строке находятся n целых чисел a_i — элементы массива (0 \leqslant a_i \leqslant 10^{5}).

В следующих q строках находятся по два целых числа: l_{i} и r_{i} — вопросы Славы, для каждого из которых необходимо посчитать сумму чисел в массиве с l_{i} по r_{i} (включая границы) (1 \leqslant l_{i} \leqslant r_{i} \leqslant n).

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

Выходные данные должны состоять из q строк, в каждой из которых должно находится по одному числу — ответы на вопросы Славы.

Примеры
Стандартный вводСтандартный вывод
5 3
1 2 3 4 5
1 3
2 4
1 5
6
9
15
Примечания

Решения, правильно работающие при 1 \leqslant n, q \leqslant 10^{3}, будут оцениваться из 30 баллов.

Решения, правильно работающие при 1 \leqslant n, q \leqslant 10^{5}, будут оцениваться из 100 баллов.