Chubaty teaches Grigory Melekhov how to perform a Baklan strike with a saber. As targets, they use n trees in a row, numbered from 1 to n. Chubaty, estimated the strength of all trees by natural numbers, and wrote them down. For each tree that Melekhov was able to cut, he receives a number of points equal to the number written on the tree, and if he could not, he loses the same amount.
Chubaty asks Grigory to hit trees from l to r, in ascending order of their numbers. Melekhov recently hurt his shoulder, so he can successfully cut down a tree every other time, i.e. if he cut down a tree with number i, then he will not be able to cut down a tree with number i + 1, but will be able to cut down the tree with number i + 2 etc.
Chubat
m once asked Grigory to perform blows, but he forgot what trees Melekhov could cut down. Help him determine how many points Gregory scored for each attempt.
Input
The first line contains 2 numbers n and m (\(1 <= n, m <= 100000 \))
The second line contains n numbers - the strength of all trees, where the strength of the tree i is written at position i.
The following m lines contain pairs of numbers l and r (\(1 < = l <= r <= n\)), meaning which piece of trees Chubaty asked to cut down.
Output
For each query print how many points Grigory earned in this attempt.
Examples
| # |
Input |
Output |
| 1 |
6 6
1 2 3 4 5 6
16
1 5
2 6
2 5
2 4
2 2
|
-3
3
4
-2
3
2
|