Аналитик работает с массивом из n целых чисел, где каждый элемент описывает некоторое числовое значение за соответствующую позицию. Ему нужно быстро отвечать на большое число запросов.

Каждый запрос задаётся двумя числами l и r и требует найти сумму элементов массива на отрезке от l до r включительно, то есть сумму a_l + a_{l+1} + ... + a_r.

Так как запросов много, требуется обработать их эффективно.

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

В первой строке заданы два целых числа n и q — размер массива и количество запросов.

Во второй строке заданы n целых чисел a_1, a_2, ..., a_n.

В следующих q строках содержится по два целых числа l и r — границы очередного запроса.

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

Для каждого запроса выведите в отдельной строке одно целое число — сумму элементов массива на отрезке [l, r].

Ограничения

• 1 <= n, q <= 2 * 10^5
• -10^9 <= a_i <= 10^9
• 1 <= l <= r <= n

Примеры

Пример 1

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

5 5
-2 0 3 -1 4
1 1
1 3
2 5
4 4
1 5

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

-2
1
6
-1
4

Пример 2

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

6 6
1000000000 -1000000000 1000000000 -1000000000 7 -7
1 2
1 4
3 6
5 6
2 2
1 6

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

0
0
0
0
-1000000000
0