题目描述

设想一条无限长的直线，初始时每个整数点的值都是0。本题涉及两类操作：

1. 增加操作：给定一个整数点 x，将其数值增加 c。共进行 n 次此类操作。
2. 区间查询：在所有增加操作后，将进行 m 次查询。每次查询指定一个起始点 l 和一个终点 r，要求返回这个区间内所有点的值之和（包含 l 和 r）。

输入格式

• 第一行包含两个整数 n 和 m，分别代表增加操作和查询的数量。
• 接下来 n 行，每行包含两个整数 x 和 c，分别表示增加操作的位置和增加的值。
• 接下来 m 行，每行包含两个整数 l 和 r，分别表示查询区间的起点和终点。

输出格式

• 对于每次查询，输出一行一个整数，代表该区间内所有点的值之和。

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

8
0
5

数据范围

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