【题目描述】

给定 $n$ 个整数和 $q$ 次询问。每次给出 $l,r$，求 $a_l+a_{l+1}+\cdots+a_r$。

【输入格式】

$n$   $q$

$a_1$   $\cdots$   $a_n$

$l_1$   $r_1$

$\vdots$

$l_q$   $r_q$

【输出格式】

每次询问输出一行区间和。

【样例】

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

5
11
3

【数据范围】

• $1\le n\le300000$
• $1\le q\le100000$
• $|a_i|\le10^9$
• $1\le l\le r\le n$