描述

给定一个长度为n的序列和m次询问
每次询问给出一个区间的左右端点l,r
对于每次询问,求序列在该区间的和

输入

第一行,两个个整数n,m
第二行,n个整数,表示给定的序列
第3到第m+2行.每行两个整数l和r,表示询问区间的端点

输出

输出共n行,每行一个整数,依次表示每个询问的结果

样例输入

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

样例输出

6
9
15

范围和限制

对于60分的数据:n<=1000,m<=1000
对于100分的数据:n<=100000,m<=200000,1<=l<r<=n,全部序列的和<10^9
时间限制1秒,空间限制256M