A. Sun
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Solaris satellite is orbiting the Sun to collect important information about the most important celestial body for Earth. To do this, the satellite collects an array of $$$n$$$ integers and sends back $$$k$$$ checksums to ensure the accuracy of the data.

Each checksum can be represented as $$$x_1 + 2x_2 + x_3 + 2x_4 + x_5 + \cdots$$$, where $$$x$$$ is an array of integers labeled $$$x_1, x_2, x_3, \cdots$$$ that is being added up, alternating between multiplying by 1 and multiplying by 2.

More formally, let the checksum of array $$$x$$$ with length $$$l$$$ be $$$f(x)$$$ where

$$$f(x) = \sum_{i=1}^{l} \left(2-\left(i \bmod 2\right)\right)\cdot x_i$$$

Given an array $$$a$$$ of $$$n$$$ integers, print out the results of $$$k$$$ checksums, where each checksum runs on a subarray of $$$a$$$ from indices $$$l_i$$$ to $$$r_i$$$ inclusive.

Input

The first line of input will consist of 2 integers, $$$n$$$ and $$$k$$$ $$$(1\leq n\leq 100, 1\leq k\leq 100)$$$.

The second line will contain the array $$$a$$$ $$$(-10^3\leq a_i\leq 10^3)$$$.

The $$$i$$$th of the next $$$k$$$ lines will contain 2 integers, $$$l_i$$$ and $$$r_i$$$ $$$(1\leq l_i\leq r_i\leq n)$$$.

Output

Output $$$k$$$ lines, each with a single integer denoting the answer to the $$$i$$$th checksum.

Example
Input
5 4
5 3 -2 1 -3
1 3
2 5
1 5
4 4
Output
9
-6
8
1
Note

The answer to the first query is 9 since $$$5+2\cdot3-2 = 9$$$.

The answer to the second query is -6 since $$$3-2\cdot2+1-2\cdot3 = -6$$$.