Чубатый учит Григория Мелехова выполнять баклановский удар шашкой. В качестве целей, они используют 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\)), означающие какой отрезок деревьев попросил срубить Чубатый.
Выходные данные
На каждый запрос выведите сколько очков в эту попытку заработал Григорий.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
6 6
1 2 3 4 5 6
1 6
1 5
2 6
2 5
2 4
2 2
|
-3
3
4
-2
3
2
|