Чубатый учит Григория Мелехова выполнять баклановский удар шашкой. В качестве целей они используют n деревьев, стоящих в ряд и пронумерованных от 1 до n. Чубатый оценил прочность всех деревьев натуральными числами и записал их. За каждое дерево, которое Мелехов смог разрубить, он получает количество очков равное числу, записанному на дереве, а если не смог - то теряет столько же.

Чубатый просит Григория выполнить удары на деревьях с l по r, в порядке возрастания их номеров. Мелехов недавно ушиб плечо, потому он может успешно срубить дерево через раз, т. е. если он срубил дерево с номером i, то он не сможет срубить дерево с номером i + 1, но сможет срубить дерево с номером i + 2 и т. д.

Мелехов m раз попросил Григория выполнить удары, но он забыл, какие деревья Мелехов смог срубить. Помогите ему определить, сколько очков набрал Григорий за каждую попытку.

 

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

В первое строке содержатся 2 числа n и m (1 <= n, m <= 100000)

Во второй строке содержатся n чисел - прочность всех деревьев, где на позиции i написана прочность дерева i.

В следующих m строках содержатся пары чисел l и r (1 <= l <= r <= n), означающие какой отрезок деревьев попросил срубить Чубатый.

 

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

На каждый запрос выведите сколько очков в эту попытку заработал Григорий.

Ввод	Вывод
6 6 1 2 3 4 5 6 1 6 1 5 2 6 2 5 2 4 2 2	57 -92 57 -130