Баланс в школьной столовой

В школьной столовой завели «дневник баланса» по дням: в какой-то день кто-то пополнил счёт (это плюс), а в какой-то списали за обеды (это минус). Классный руководитель часто спрашивает: «А какой итог был за дни с L по R включительно?»

Тебе нужно быстро отвечать на такие вопросы.

Формат ввода

В первой строке даны два целых числа n и q — число дней и число вопросов. Во второй строке даны n целых чисел a1, a2, ..., an — изменения баланса по дням. В следующих q строках даны пары целых чисел L R (1 ≤ L ≤ R ≤ n) — границы отрезка дней.

Формат вывода

Для каждого вопроса выведи одно целое число — сумму aL + a(L+1) + ... + aR.

Ограничения

• 2 ≤ n ≤ 16000
• 1 ≤ q ≤ 16000
• -1 000 000 ≤ ai ≤ 1 000 000
• 1 ≤ L ≤ R ≤ n

Пример

Ввод:

5 3
10 -7 2 0 5
1 3
2 5
4 4

Вывод:

5
0
0

Ключевое наблюдение: сумму на отрезке L..R удобно получать не складыванием всех элементов, а «вычитанием лишнего» из накопленных сумм.

Заведём массив префиксных сумм pref, где pref[i] — сумма изменений за первые i дней (от 1 до i). Тогда сумма на любом отрезке L..R равна: pref[R] - pref[L-1]. Это работает, потому что в pref[R] сидит сумма 1..R, а в pref[L-1] — ровно то, что нужно убрать (1..L-1).

План решения:

• Прочитай n и q, затем массив a[1..n].
• Создай pref длины n+1, положи pref[0] = 0.
• Для i от 1 до n посчитай pref[i] = pref[i-1] + a[i].
• Для каждого запроса (L, R): выведи pref[R] - pref[L-1].

Сложность: построение pref — O(n), каждый запрос — O(1), итого O(n + q) вместо O(n*q).

Частая ошибка: забыть про pref[0] = 0 и сдвиг индексов (особенно в Python со списками с 0). Формула именно pref[R] - pref[L-1], иначе запросы с L=1 ломаются.