Description

给定 n 个可能为负数的整数，回答 q 次区间和询问。

Input Format

第一行两个整数 n 和 q。第二行 n 个整数。接下来 q 行，每行两个整数 l 和 r。

Output Format

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

6 2
-5 10 -3 8 -2 7
1 2
2 5

5
13

Hint

负数不会影响前缀和公式，但要注意 long long。