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

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

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

输入格式

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

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

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

输出格式

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

数据范围

$-10^9 \le x \le 10^9$,
$1 \le n,m \le 10^5$,
$-10^9 \le l \le r \le 10^9$,
$-10000 \le c \le 10000$

输入样例：

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

输出样例：

8
0
5

数据 1（样例风格+额外查询）：基础正确性；卡“区间包含端点/只统计更新点/输出行数不对”。

数据 2（同一坐标多次更新）：卡“把更新当成赋值覆盖而不是累加”“同一 x 只保留一次导致错”。

数据 3（含负坐标与负权值）：卡“坐标/前缀只支持非负”“用数组直接开到 1e9 或偏移处理错”。

数据 4（查询区间与所有更新点都不相交）：卡“没处理空贡献区间导致乱输出/前缀初始化错误”，正确应全为 0。

数据 5（极限边界：±1e9，超大区间）：卡边界范围、以及结果可能很大但应使用 64 位（long long）。

数据 6（n=1e5, m=1e5 压测）：强力卡复杂度：

暴力逐查询遍历所有点/排序后每次扫描会 TLE

必须用 坐标离散化 + 前缀/树状数组，整体约 O((n+m) log (n+m))

数据 7（必须包含 l-1 的离散化陷阱）：卡常见错法：离散化只收集 x,l,r，但用前缀计算 sum(r)-sum(l-1) 时 l-1 不在坐标里 导致结果错。

数据 8（大量正负抵消、c=±10000 边界）：卡符号处理、叠加抵消、以及单点区间与跨区间混合查询。