1417 - 前缀和

给出n个数字,m次询问,每次询问下标区间[l,r]内数字的和

Input

第一行两个整数n,m
第二行n个整数x
接下来m行,每行两个整数l,r

Output

对于每个询问输出一行,表示数字和

Examples

Input

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

Output

15
5
12
Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题