题目描述

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

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

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

输入格式

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

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

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

数据范围：-1e9 <= x <= 1e9，1 <= n, m <= 1e5，-1e9 <= l <= r <= 1e9，-1e5 <= c <= 1e5。

输出格式

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

样例输入

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

样例输出

8
0
5

样例解释

初始时，数轴上所有位置的数都是 0。

1. 第一次操作：位置 1 加 2，数轴上位置 1 的数变为 2。
2. 第二次操作：位置 3 加 6，数轴上位置 3 的数变为 6。
3. 第三次操作：位置 7 加 5，数轴上位置 7 的数变为 5。

接下来进行三次询问：

• 第一次询问区间 [1, 3]：位置 1 的数是 2，位置 2 的数是 0，位置 3 的数是 6，总和为 2 + 0 + 6 = 8。
• 第二次询问区间 [4, 6]：位置 4、5、6 的数都是 0，总和为 0。
• 第三次询问区间 [7, 8]：位置 7 的数是 5，位置 8 的数是 0，总和为 5 + 0 = 5。

因此，三次询问的结果分别是 8、0、5。