#2066. 区间和

区间和

问题描述

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

现在,我们首先进行nn次操作,每次操作将某一位置xx上的数加cc

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

输入格式

第一行包含两个整数nnmm

接下来nn行,每行包含两个整数xxcc

再接下来mm行,每行包含两个整数llrr

输出格式

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

数据范围

109x109,−10^9≤x≤10^9, 1n,m105,1≤n,m≤10^5, 109lr109,−10^9≤l≤r≤10^9,10000c1000010000≤c≤10000

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