Description

“糟了！离 同学，是范围陷阱卡。大家快散 开！”七海同学喊道。

“来不及了，不愧是高位陷阱卡，范围根本存不下。大家别动！现在，就要讲究一个字——化 ，化劲。易有太极，是生两仪，两仪生四象，四象生八卦，喝啊！开！”只见离同学的手高速刺出，化为残影，攻击陷阱卡的各个部位。

“增删！求和！ ”一阵金光闪过，陷阱卡化为乌有，危机解除了。

“真是太厉害了！离同学，你是怎么做到的？”

“桀桀，你可以问问屏幕前的高人，他一定会为你细心解答。”

假设这个陷阱卡如同一个无限长的数轴，数轴上每个坐标上的数都是0.

离同学对它进行了n次操作，每次操作将某一位置x上的数加c。

同时也进行m次询问，每个询问包含两个整数l和r，求出了在区间[l,r]之间的所有数的和。

请高人你根据离同学的操作和询问，给出相应的正确答案，以博得七海娜娜米同学的欢心（bushi）。

Format

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

Hint

数据范围****

−10 ^9≤x≤10^9,
1≤n,m≤10^5,
−10^9≤l≤r≤10^9,
−10000≤c≤10000