这是一道模板题。记下标从 1 开始，给定长为 n 的数组 a。你需要求 m 次区间 [l,r] 的和，即求 \sum_{i=l}^ra_i。
输入
输入一行两个整数 n,m(1\le n,m\le 10^5)。
接下来输入一行 n 个整数，第 i 个整数为 a_i(-10^9\le a_i\le 10^9)。
接下来输入 m 行，每行两个整数 l,r(1\le l\le r \le n)，代表一次询问。
输出
对于每次询问，输出一行一个整数 \sum_{i=l}^ra_i。
样例
| 标准输入 复制文本 |
6 2 1 1 4 5 1 4 1 6 4 5 |
| 标准输出 复制文本 |
16 6 |