计算区间和

输入 $n$ 个整数，再输入m个区间，每个区间的起点下标L，终点下标R。
对于每个区间，输出n个整数中从下标L到下标R的区间和。

输入格式

第一行包括两个整数n和m。（1≤n,m≤500000） 第二行包括n个整数。（1≤整数≤100） 接下来有m行，每行包含两个整数L和R，表示区间范围。（0<L≤R≤n）

输出格式

输出有m行，每行一个整数，表示一个区间和。

10 3
2 1 3 6 4 20 15 10 4 11
3 7
1 9
5 8

48
65
49

数据范围

时间限制: 1000ms

内存限制: 256MB