C. Выигранный спор ограничение по времени на тест1.0 с

ограничение по памяти на тест256 мегабайт

вводстандартный ввод

выводстандартный вывод

Недавно Азамат гуляя по кампусу университета увидел как группа парней пытаются решить одну задачу. Он поспорил что решит эту задачу в течении 1 дня, решил показаться крутым, но в итоге он понял, что не справится, поэтому решил попросить у вас.

Задача состоит в следующем. Ребята нашли список того, что будут давать в столовой в ближайшие n дней. Главный из ребят указал насколько ему нравится то, что будет в определенный день. Теперь он думает насколько ему понравятся блюда на определенном отрезке дней.

Формально, вам задан массив a длины n. Также вам дается q запросов. Каждый запрос состоит из отрезка l,r. Надо посчитать сумму на этом отрезке.

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

Первая строка состоит из двух целых чисел n (1<=n<=100000), q (1<=q<=100000). Вторая строка состоит из n чисел - массив a В следующих q строках дается l, r (1<=l<=r<=n)

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

Вывести q строк - сумму на каждом отрезке