Description

给定一个长度为 n 的整数序列，接着有 q 次询问。每次询问给出 l 和 r，请输出第 l 个数到第 r 个数的和。

Input Format

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

Output Format

输出 q 行，每行一个整数，表示对应区间和。

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

6
14
4

Hint

使用 1 下标前缀和：sum[r]-sum[l-1]。注意答案可能超过 int。