Background

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

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

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

Input

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

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

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

Output

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

Samples

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

8
0
5

Limitation

$−10^9≤x≤10^9,$

$1≤n,m≤10^5$

$−10^9≤l≤r≤10^9$

$−10000≤c≤10000$