802. 区间和

假定有一个无限长的数轴,数轴上每个坐标上的数都是0。

现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。

近下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。

输入格式

第一行包含两个整数n和m。

接下来 n 行,每行包含两个整数x和c。

再接下里 m 行,每行包含两个整数l和r。

输出格式

共m行,每行输出一个询问中所求的区间内数字和。

数据范围

$-10^9 \le x \le 10^9$,
$1 \le n,m \le 10^5$,
$-10^9 \le l \le r \le 10^9$,
$-10000 \le c \le 10000$

输入样例:

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例:

8
0
5