Физик проводит серию измерений заряда на последовательных моментах времени. Для каждого момента времени i известно значение a_i.

Из-за особенностей оборудования полярность зонда при обработке результатов должна чередоваться. Поэтому для любого отрезка времени от l до r интерес представляет не обычная сумма, а чистый заряд, вычисляемый так, что на позиции l стоит знак «+», на позиции l + 1 — знак «-», затем снова «+» и так далее:

a_l - a_{l+1} + a_{l+2} - a_{l+3} + ... ± a_r

Требуется ответить на q запросов. В каждом запросе заданы два числа l и r (1 <= l <= r <= n). Для каждого запроса выведите чистый заряд на этом отрезке при чередующейся полярности, начинающейся со знака «+» в момент l.

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

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

Вторая строка содержит n целых чисел a_i — результаты измерений заряда.

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

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

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

Ограничения

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

Примеры

Пример 1

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

5 7
1 2 3 4 5
1 1
1 2
2 5
3 3
1 5
4 5
2 2

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

1
-1
-2
3
3
-1
2

Пример 2

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

6 8
-5 0 7 -3 2 -8
1 6
2 6
1 3
4 6
5 5
2 3
3 4
6 6

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

15
-20
2
-13
2
-7
10
-8