You are given an array $a$ of length $n$. You are to answer $q$ queries of the type:

• l r - Find $\displaystyle\sum_{i=l}^r a_i$, the sum of the subarray $a[l..r]$.

Input

The first line of input consists of two integers, $n$ and $q.$
The second line of input consists of $n$ integers, $a_1, a_2, \dots, a_n.$
$q$ lines of input follow. The $(i+2)$th line of input consists of the integers $l_i$ and $r_i$, the parameters to the $i$th query.

Output

On the $i$th line, output the answer to the $i$th query.

Constraints

$1 \le n,q \le 10^5$
$0 \le a_i \le 10^{12}$
$1 \le l_i \le r_i \le n$