题目描述

在一个神秘的魔法世界里，有一条魔法长廊，长廊上依次排列着n个魔法水晶柱，编号从1到n。每个魔法水晶柱都蕴藏着不同程度的魔法能量，第i个水晶柱的魔法能量值为 ai。

现在有一群魔法师来探索这个魔法长廊，他们会进行m次魔法探索行动。每次行动，魔法师们会从第l个水晶柱走到第r个水晶柱（包含第l个和第 r个），并收集这段路径上的魔法能量。不过，魔法能量的收集规则有些特殊：

如果从第l个到第r个水晶柱的数量为奇数，那么收集到的魔法能量总和需要额外加上这段区间内所有偶数能量值水晶柱的能量值。

如果数量为偶数，那么收集到的魔法能量总和需要额外减去这段区间内所有奇数能量值水晶柱的能量值。

请你编写一个程序，帮助魔法师们计算每次魔法探索行动能收集到的魔法能量总和。

输入格式

第一行包含两个整数 n和m（1≤n≤105，1≤m≤105），分别表示魔法水晶柱的数量和魔法探索行动的次数。第二行包含 n个整数a1,a2,⋯,an（0≤ai≤1000），表示每个魔法水晶柱的魔法能量值。接下来的m行，每行包含两个整数l和r（1≤l≤r≤n），表示每次魔法探索行动的起始和结束水晶柱编号。 输出格式

输出

m行，每行一个整数，表示每次魔法探索行动能收集到的魔法能量总和。

样例输入

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

样例输出

9 6 9